曾经，农民需要在河上运送狼，山羊和白菜。农民有一艘船，除了农民本人以外，只能容纳一个物体-狼，山羊或白菜。如果农民在狼人无人看管的情况下离开狼，狼就会吃掉山羊。如果一个农民在无人看管的情况下给山羊留下了白菜，那么山羊会吃掉白菜。
在本文中，我们将尝试通过使用代数效应为这种类型的难题找到一个通用的解决方案。
让我们从最简单的路线开始-行驶路线。由于我们事先不知道要保证多少步数才能得到解决方案，因此我们可以建立一条无限路线，无论如何我们都会懒洋洋地计算出来：
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.
在代码中，我将使用实验性的联合库（Habré上有两篇文章解释了其本质，第一篇和第二篇），但是如果需要，可以将解决方案转移到互感器或mtl。
因此，我们有三种不同的影响：状态，多重性和局部性。现在，我们需要决定如何将它们安排在一起：
- 在Maybe的应用/单子评估链中，如果我们什么都没有，那么所有计算的结果将为Nothing。我们将单独放置它，因为我们不希望在发送空船时（没有角色，没有农民，我们没有考虑到），我们将在寻找解决方案方面失去所有进展。
- 后续的每个移动选择（多重效果）都必须取决于当前海岸的构成（状态效果），因为如果角色在另一岸上，我们就无法将角色带入船中。因此，我们需要将这些影响串联到一个转换器中：State（River a）：> []。
难题中的一招可以描述为一系列动作：
- 获取当前岸上的角色阵容
- 选择下一个要运输的角色
- 将角色移到对岸
step direction = bank >>= next >>= transport让我们更详细地完成每个步骤。
根据船的运动方向，我们将透镜用作整个河流州的出发源，并获得当前河岸的组成：
bank :: (Functor t, Stateful (River a) t) => t [a]
bank = view (source direction) <$> current
下一个字符的选择是这样的：从岸边（上一个表达式库）接收一组字符，我们通过向该空间本身添加空船来形成选择空间：
\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)
最后一步-使用镜头进行实际运输：从发货银行中删除字符，然后添加到目标银行中：
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
我们有两种解决方案：
完整资源可以在这里查看。