[Haskell, Алгоритмы, Функциональное программирование] Перевозим волка, козу и капусту через реку с эффектами на Haskell
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
Однажды крестьянину понадобилось перевезти через реку волка, козу и капусту. У крестьянина есть лодка, в которой может поместиться, кроме самого крестьянина, только один объект — или волк, или коза, или капуста. Если крестьянин оставит без присмотра волка с козой, то волк съест козу; если крестьянин оставит без присмотра козу с капустой, коза съест капусту.
В этой статье мы попытаемся найти обобщенное решение для такого типа головоломок и для этого будем использовать алгебраические эффекты.
Начнем с самого простого — маршрута перемещений. Так как мы не знаем заранее, через какое гарантированное количество шагов мы получим решение, можно построить бесконечный маршрут, все равно мы будем вычислять его лениво:
data Direction = Back | Forward
route :: [Direction]
route = iterate alter Forward
alter :: Direction -> Direction
alter Back = Forward
alter Forward = Back
Так как мы собираемся построить обобщенное решение, то и абстрагируемся от персонажей тоже. Мы построим нетранзитивное симметричное отношение порядка между элементами множества персонажей (поделитесь в комментариях, если для этого есть свое устоявшееся название):
data Character = Wolf | Goat | Cabbage deriving Eq
class Survivable a where
survive :: a -> a -> Ordering
instance Survivable Character where
survive Wolf Goat = GT
survive Goat Wolf = LT
survive Goat Cabbage = GT
survive Cabbage Goat = LT
survive _ _ = EQ
Зачем вообще использовать эффекты? Эффекты помогают бороться со сложностью, которая присуща любой предметной области. Значит, для того, чтобы определить какие эффекты использовать для решения головоломки, стоит подумать над тем, с какими сложностями мы можем столкнуться, когда попробуем описать решение задачи с помощью кода:
- Чтобы найти решение, при котором все персонажи будут перевезены на противоположный берег, надо перебрать много вариантов перестановок. Для этого мы будем использовать эффект множественности, которого можно добиться с помощью обычного списка.
- Еще нам нужно запоминать местоположение персонажа, чтобы проверять условия совместимости с другими персонажами (волк ест козу, коза ест капусту) и кого можно посадить на лодку. Мы можем хранить состав двух берегов type River a = ([a],[a]) c помощью эффекта состояния State (River a).
- Лодка может взять кого-нибудь на борт, а может и не брать — тут нам пригодится эффект частичности с Maybe.
В коде я буду использовать свою экспериментальную библиотеку joint (на Хабре есть две статьи, объясняющие ее суть — первая и вторая), но при желании решение можно перенести на transformers или mtl.
Итак, у нас есть три разрозненных эффекта: состояние, множественность, частичность. Теперь надо решить, как мы собираемся их скомпоновать между собой:
- В аппликативной/монадной цепочке вычислений для Maybe, если мы где-то получили Nothing, то и результат всего вычислений будет Nothing. Мы оставим его отдельно, так как не хотим, чтобы при отправлении пустой лодки (без персонажа, крестьянина мы не учитываем) мы потеряли весь прогресс в нахождении решения.
- Каждый последующий выбор хода (эффект множественности) должен опираться на состав текущего берега (эффект состояния), так как мы не можем взять персонажа в лодку, если она находится на другом берегу. Следовательно, нам нужно эти эффекты сцепить в трансформер: State (River a) :> [].
Один ход в головоломке можно описать как последовательность действий:
- Получить состав персонажей на текущем берегу
- Выбрать следующего персонажа для транспортировки
- Переместить персонажа на противоположный берег
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 -> Bool
valid Nothing = and $ coexist <$> xs <*> xs
valid (Just x) = and $ coexist <$> delete x xs <*> delete x xs
coexist :: Survivable a => a -> a -> Bool
coexist 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 a
leave = source direction %~ delete x
land = 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 where
transport Nothing = pure Nothing
Было бы неплохо посмотреть на работу программы в действии. Для нахождения решения нам нужно как минимум совершить семь шагов по маршруту:
start :: River Character
start = ([Goat, Wolf, Cabbage], [])
solutions = run (traverse step $ take 7 route) start
И у нас есть два решения:
Полные исходник можно посмотреть здесь.
===========
Источник:
habr.com
===========
Похожие новости:
- [Алгоритмы, Искусственный интеллект, Обработка изображений] МТИ и Microsoft обучили алгоритм находить скрытые параллели между картинами
- [GitHub, Python, SQLite, Алгоритмы, Веб-аналитика] Как проанализировать рынок фотостудий с помощью Python (2/3). База данных
- [.NET, C#, Алгоритмы, Разработка игр] A* pathfinding на C#: двоичные кучи и борьба с аллокациями
- [Алгоритмы, Звук] Алгоритмизируем музыку
- [Разработка веб-сайтов, Python, Программирование, Функциональное программирование] Какая асинхронность должна была бы быть в Python
- [Алгоритмы, Законодательство в IT, Математика] Опубликован алгоритм генерации уникальных 11-разрядных номеров жителям РФ
- [Алгоритмы, Здоровье, Информационная безопасность, Искусственный интеллект, Исследования и прогнозы в IT] NIST: медицинские маски нарушают работу систем распознавания лиц
- [C, Алгоритмы] Алгоритм сортировки quadsort (перевод)
- [Java, Алгоритмы] Побитовая арифметика в Java
- [Scala, Функциональное программирование] Fetch — библиотека для доступа к данным
Теги для поиска: #_haskell, #_algoritmy (Алгоритмы), #_funktsionalnoe_programmirovanie (Функциональное программирование), #_haskell, #_functor, #_applicative, #_monad, #_traversable, #_haskell, #_algoritmy (
Алгоритмы
), #_funktsionalnoe_programmirovanie (
Функциональное программирование
)
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 23-Ноя 01:25
Часовой пояс: UTC + 5
| Автор | Сообщение |
|---|---|
|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
|
Однажды крестьянину понадобилось перевезти через реку волка, козу и капусту. У крестьянина есть лодка, в которой может поместиться, кроме самого крестьянина, только один объект — или волк, или коза, или капуста. Если крестьянин оставит без присмотра волка с козой, то волк съест козу; если крестьянин оставит без присмотра козу с капустой, коза съест капусту.
 В этой статье мы попытаемся найти обобщенное решение для такого типа головоломок и для этого будем использовать алгебраические эффекты. Начнем с самого простого — маршрута перемещений. Так как мы не знаем заранее, через какое гарантированное количество шагов мы получим решение, можно построить бесконечный маршрут, все равно мы будем вычислять его лениво: data Direction = Back | Forward
route :: [Direction] route = iterate alter Forward alter :: Direction -> Direction alter Back = Forward alter Forward = Back Так как мы собираемся построить обобщенное решение, то и абстрагируемся от персонажей тоже. Мы построим нетранзитивное симметричное отношение порядка между элементами множества персонажей (поделитесь в комментариях, если для этого есть свое устоявшееся название): data Character = Wolf | Goat | Cabbage deriving Eq
class Survivable a where survive :: a -> a -> Ordering instance Survivable Character where survive Wolf Goat = GT survive Goat Wolf = LT survive Goat Cabbage = GT survive Cabbage Goat = LT survive _ _ = EQ Зачем вообще использовать эффекты? Эффекты помогают бороться со сложностью, которая присуща любой предметной области. Значит, для того, чтобы определить какие эффекты использовать для решения головоломки, стоит подумать над тем, с какими сложностями мы можем столкнуться, когда попробуем описать решение задачи с помощью кода:
В коде я буду использовать свою экспериментальную библиотеку joint (на Хабре есть две статьи, объясняющие ее суть — первая и вторая), но при желании решение можно перенести на transformers или mtl. Итак, у нас есть три разрозненных эффекта: состояние, множественность, частичность. Теперь надо решить, как мы собираемся их скомпоновать между собой:
Один ход в головоломке можно описать как последовательность действий:
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 -> Bool
valid Nothing = and $ coexist <$> xs <*> xs valid (Just x) = and $ coexist <$> delete x xs <*> delete x xs coexist :: Survivable a => a -> a -> Bool coexist 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 a
leave = source direction %~ delete x land = 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 where transport Nothing = pure Nothing Было бы неплохо посмотреть на работу программы в действии. Для нахождения решения нам нужно как минимум совершить семь шагов по маршруту: start :: River Character
start = ([Goat, Wolf, Cabbage], []) solutions = run (traverse step $ take 7 route) start И у нас есть два решения:  Полные исходник можно посмотреть здесь. =========== Источник: habr.com =========== Похожие новости:
Алгоритмы ), #_funktsionalnoe_programmirovanie ( Функциональное программирование ) |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 23-Ноя 01:25
Часовой пояс: UTC + 5