The task of the missionaries and cannibals in the language Haskell

Studying the Haskell language, I once again faced the problem of finding some task for practicing new skills. After some hesitation, it was decided to implement a wide search algorithm written long time ago in python for the problem of crossing missionaries and cannibals. The decision seemed to me rather concise, therefore I decided to share it with people (and at the same time listen to criticism).

Interested please follow under cat.

Task statement

Three missionaries and three cannibals must be shipped from one bank of the river to the other. In the boat on which they will move, only two people can simultaneously fit, and if during the movement the number of cannibals on the same bank exceeds the number of missionaries, the missionaries will be eaten (which, of course, must be avoided). It is necessary to find a sequence of safe (not leading missionaries to the sad fate of James Cook) transportation.

Decision

The theater begins with a hanger, and the Haskell program begins with the import of modules necessary for the work. Let's start with them.

import Data.List 

To store information about the location of the missionaries, cannibals and the shore where the boat is located, we will define our data type.
')

 data State = State { missioners :: Int, cannibals :: Int, bank :: Char} deriving (Eq, Show) 

The attentive reader may ask: “But why in the State there are only two integer fields? Missionaries may be on the left bank or on the right; The same applies to cannibals. It turns out four numeric fields. ”
True remark, but for certain reasons, information about the number of people on the coast without a boat is redundant (for what - it will be said a little lower).

In order for our boat to sail from one bank to another, it is necessary to specify all possible movements. There are only five of them:

 move01 (State msn cnb bk) = State (3 - msn + 2) (3 - cnb) (oppositeBank bk) move02 (State msn cnb bk) = State (3 - msn) (3 - cnb + 2) (oppositeBank bk) move03 (State msn cnb bk) = State (3 - msn + 1) (3 - cnb + 1) (oppositeBank bk) move04 (State msn cnb bk) = State (3 - msn + 1) (3 - cnb) (oppositeBank bk) move05 (State msn cnb bk) = State (3 - msn) (3 - cnb + 1) (oppositeBank bk) 

Do you notice? We do not need to keep information about how many missionaries we have on the opposite bank - we can always get their number by subtracting the number of missionaries on the current bank from three. The same applies to cannibals.

oppositeBank is the simplest function that changes the label of the coast to the opposite.

 oppositeBank :: Char -> Char oppositeBank bank | bank == 'L' = 'R' | otherwise = 'L' 

Having created a new state, we have to check whether it is possible (in other words, have we come up with a situation where four missionaries turned out to be on the bank with the boat, or, even more fun, one and a half woodcutter minus one cannibal).

 isStatePossible :: State -> Bool isStatePossible (State msn cnb bk) = msn >= 0 && msn <= 3 && cnb >= 0 && cnb <= 3 

You must also check whether the state is safe. There are three possible options. The first is the number of cannibals equal to the number of missionaries. The second is that there are three missionaries on the current bank (in this case there are no missionaries on the opposite bank and the situation is safe). The third is the opposite of the second - all the missionaries gathered on the opposite bank.
So we write.

 isStateSafe :: State -> Bool isStateSafe (State msn cnb bk) = (cnb == msn) || (msn == 3) || (msn == 0) 

Now we go to the most important thing - the search in width. About what it is, you can find out by clicking on the link , but I will focus on the description of the implementation.

 bfsSolution :: [[State]] -> [State] bfsSolution (path:tail') | State 3 3 'R' `elem` extensions = State 3 3 'R' : path | otherwise = bfsSolution $ tail' ++ [ext : path | ext <- extensions, (not . elem ext) path] where headState = head path extensions = filter (\x -> isStatePossible x && isStateSafe x) [move01 headState, move02 headState, move03 headState, move04 headState, move05 headState] 

bfsSolution is a recursive procedure. First of all, we take the path in the head from the list of paths already built. We are trying to continue it by building all possible (and safe) continuations. If one of the constructed continuations is the final state, the procedure ends its work and returns to the continued path. Otherwise, we add all the generated paths to the tail of the list and call the procedure again.
Very important is the condition

 (not . elem ext) path 

It does not allow returning to one of the states passed by the algorithm in the process of building this path. For example, if at step n we sent two missionaries from the left bank to the right bank, then at step (n + 1) there is no point in returning them back to the left bank - we will waste time and do not move the solution a single step (the above program finds on my netbook, the solution is 0.85 seconds; by removing the above condition, I get a hefty increase in computations — it takes 45 seconds to find the answer).

The final touch is the main function.

 main = do mapM_ (putStrLn . show) $ (reverse . bfsSolution) ([[State 3 3 'L']]) 

Conclusion

This article in no way claims to complete the review and an exhaustive explanation of all possible solutions to this problem. Interested readers can implement a depth-first search algorithm with returns; There is also another (not yet implemented) idea on “bringing to mind” the above solution - try to move away from storing all the generated solutions in the list of lists and implement the n-ary tree.

Thanks for attention.