Transporting a wolf, a goat and a cabbage across the river with effects in Haskell

Once a peasant needed to transport a wolf, a goat and a cabbage across the river. The peasant has a boat in which, besides the peasant himself, only one object can fit - either a wolf, or a goat, or a cabbage. If the peasant leaves the wolf with the goat unattended, the wolf will eat the goat; if a peasant leaves a goat with cabbage unattended, the goat will eat the cabbage.

In this article, we will try to find a generalized solution for this type of puzzle by using algebraic effects.



Let's start with the simplest one - the travel route. Since we do not know in advance what guaranteed number of steps we will get the solution after, we can build an infinite route, anyway we will calculate it lazily:

data Direction = Back | Forward

route :: [Direction]
route = iterate alter Forward

alter :: Direction -> Direction
alter Back = Forward
alter Forward = Back

Since we are going to build a generalized solution, we also abstract from the characters. We will build a non-transitive symmetric order relation between the elements of a set of characters (share in the comments if there is a well-established name for this):

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

Why use effects at all? Effects help combat the complexity inherent in any domain. So, in order to determine what effects to use to solve the puzzle, it is worth thinking about what difficulties we may face when we try to describe the solution to the problem using code:

• , , . , .
• , ( , ) . type River a = ([a],[a]) c State (River a).
• - , — Maybe.

In the code, I will use my experimental joint library (there are two articles on Habré explaining its essence - the first and the second ), but if desired, the solution can be transferred to transformers or mtl .



So we have three disparate effects: state, multiplicity, and partial. Now we need to decide how we are going to arrange them together:

• In the applicative / monad chain of evaluations for Maybe , if we got Nothing somewhere, then the result of all computations will be Nothing . We will leave it separately, because we do not want that when sending an empty boat (without a character, a peasant, we do not take into account) we will lose all progress in finding a solution.
• Each subsequent choice of move (multiplicity effect) must rely on the composition of the current shore (state effect), since we cannot take the character into the boat if it is on the other shore. Therefore, we need to concatenate these effects into a transformer: State (River a):> [] .

One move in a puzzle can be described as a sequence of actions:

1. Get the cast of characters on the current shore
2. Choose the next character to transport
3. Move character to the opposite bank

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

Let's go through each step in more detail.



Depending on the direction of movement of the boat, we apply the lens for the source of departure to the state of the entire river and get the composition of the current bank:

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

The choice of the next character goes like this: receiving a set of characters from the shore (the previous expression bank ), we form a selection space by adding an empty boat to this space itself:

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

For each candidate (an empty boat ( Nothing ) is also a candidate), we check that there are no characters on the remaining shore who would not mind eating each other:

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

And when we filtered out the character selection space, we raise the multiplicity effect and return each item from that selection space:

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

The last step remains - the actual transportation using lenses: remove the character from the dispatch bank and add to the destination bank:

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

If there was a character in the boat, we change the state of the river, otherwise the move was idle:

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

It would be nice to see the program in action. To find a solution, we need to take at least seven steps along the route:

start :: River Character
start = ([Goat, Wolf, Cabbage], [])

solutions = run (traverse step $ take 7 route) start

And we have two solutions:







Full sources can be viewed here .