Русский
Русский
English
Статистика
Реклама

Перевозим волка, козу и капусту через реку с эффектами на Haskell

Однажды крестьянину понадобилось перевезти через реку волка, козу и капусту. У крестьянина есть лодка, в которой может поместиться, кроме самого крестьянина, только один объект или волк, или коза, или капуста. Если крестьянин оставит без присмотра волка с козой, то волк съест козу; если крестьянин оставит без присмотра козу с капустой, коза съест капусту.




В этой статье мы попытаемся найти обобщенное решение для такого типа головоломок и для этого будем использовать алгебраические эффекты.



Начнем с самого простого маршрута перемещений. Так как мы не знаем заранее, через какое гарантированное количество шагов мы получим решение, можно построить бесконечный маршрут, все равно мы будем вычислять его лениво:

data Direction = Back | Forwardroute :: [Direction]route = iterate alter Forwardalter :: Direction -> Directionalter Back = Forwardalter Forward = Back


Так как мы собираемся построить обобщенное решение, то и абстрагируемся от персонажей тоже. Мы построим нетранзитивное симметричное отношение порядка между элементами множества персонажей (поделитесь в комментариях, если для этого есть свое устоявшееся название):

data Character = Wolf | Goat | Cabbage deriving Eqclass Survivable a wheresurvive :: a -> a -> Orderinginstance Survivable Character wheresurvive Wolf Goat = GTsurvive Goat Wolf = LTsurvive Goat Cabbage = GTsurvive Cabbage Goat = LTsurvive _ _ = EQ


Зачем вообще использовать эффекты? Эффекты помогают бороться со сложностью, которая присуща любой предметной области. Значит, для того, чтобы определить какие эффекты использовать для решения головоломки, стоит подумать над тем, с какими сложностями мы можем столкнуться, когда попробуем описать решение задачи с помощью кода:

  • Чтобы найти решение, при котором все персонажи будут перевезены на противоположный берег, надо перебрать много вариантов перестановок. Для этого мы будем использовать эффект множественности, которого можно добиться с помощью обычного списка.
  • Еще нам нужно запоминать местоположение персонажа, чтобы проверять условия совместимости с другими персонажами (волк ест козу, коза ест капусту) и кого можно посадить на лодку. Мы можем хранить состав двух берегов type River a = ([a],[a]) c помощью эффекта состояния State (River a).
  • Лодка может взять кого-нибудь на борт, а может и не брать тут нам пригодится эффект частичности с Maybe.


В коде я буду использовать свою экспериментальную библиотеку joint (на Хабре есть две статьи, объясняющие ее суть первая и вторая), но при желании решение можно перенести на transformers или mtl.

Итак, у нас есть три разрозненных эффекта: состояние, множественность, частичность. Теперь надо решить, как мы собираемся их скомпоновать между собой:

  • В аппликативной/монадной цепочке вычислений для Maybe, если мы где-то получили Nothing, то и результат всего вычислений будет Nothing. Мы оставим его отдельно, так как не хотим, чтобы при отправлении пустой лодки (без персонажа, крестьянина мы не учитываем) мы потеряли весь прогресс в нахождении решения.
  • Каждый последующий выбор хода (эффект множественности) должен опираться на состав текущего берега (эффект состояния), так как мы не можем взять персонажа в лодку, если она находится на другом берегу. Следовательно, нам нужно эти эффекты сцепить в трансформер: State (River a) :> [].


Один ход в головоломке можно описать как последовательность действий:

  1. Получить состав персонажей на текущем берегу
  2. Выбрать следующего персонажа для транспортировки
  3. Переместить персонажа на противоположный берег


step direction = bank >>= next >>= transport


Давайте пройдемся по каждому шагу подробнее.

В зависимости от направления перемещения лодки, применяем линзу для источника отправления к состоянию всей реки и получаем состав текущего берега:

bank :: (Functor t, Stateful (River a) t) => t [a]bank = view (source direction) <$> current


Выбор следующего персонажа происходит так: получая набор персонажей с берега (предыдущее выражение bank), мы формируем пространство выбора, добавляя к этому самому пространству пустую лодку:

\xs -> Nothing : (Just <$> xs) 


Для каждого кандидата (пустая лодка (Nothing) тоже кандидат) проверяем чтобы на оставшемся берегу не оставалось персонажей, которые были бы не прочь полакомиться друг другом:

valid :: Maybe a -> Boolvalid Nothing = and $ coexist <$> xs <*> xsvalid (Just x) = and $ coexist <$> delete x xs <*> delete x xscoexist :: Survivable a => a -> a -> Boolcoexist x y = survive x y == EQ


И когда мы отфильтровали пространство выбора персонажей, поднимаем эффект множественности и возвращаем каждый элемент из этого пространства выбора:

next :: (Survivable a, Iterable t) => [a] -> t (Maybe a)next xs = lift . filter valid $ Nothing : (Just <$> xs)


Остался последний шаг фактическая транспортировка c помощью линз: удаляем персонажа с берега отправки и добавляем к берегу назначения:

leave, land :: River a -> River aleave = source direction %~ delete xland = target direction %~ (x :)


Если в лодке был персонаж изменяем состояние реки, иначе ход был холостым:

transport :: (Eq a, Applicative t, Stateful (River a) t) => Maybe a -> t (Maybe a)transport (Just x) = modify @(River a) (leave . land) $> Just x wheretransport Nothing = pure Nothing


Было бы неплохо посмотреть на работу программы в действии. Для нахождения решения нам нужно как минимум совершить семь шагов по маршруту:

start :: River Characterstart = ([Goat, Wolf, Cabbage], [])solutions = run (traverse step $ take 7 route) start


И у нас есть два решения:



Полные исходник можно посмотреть здесь.
Источник: habr.com
К списку статей
Опубликовано: 02.08.2020 16:06:23
0

Сейчас читают

Комментариев (0)
Имя
Электронная почта

Haskell

Алгоритмы

Функциональное программирование

Functor

Applicative

Monad

Traversable

Категории

Последние комментарии

© 2006-2021, personeltest.ru