Today we’re going to learn to solve the classic and ageless logic problems without any data structures besides List’s monadic properties as a MonadPlus!
We are going to be solving this old-as-time logic puzzle, which Wikipedia claims dates back to the 9th century:
A farmer has a wolf, a goat, and a cabbage that he wishes to transport across a river. Unfortunately, his boat can carry only one thing at a time with him. He can’t leave the wolf alone with the goat, or the wolf will eat the goat. He can’t leave the goat alone with the cabbage, or the goat will eat the cabbage. How can he properly transport his belongings to the other side one at a time, without any disasters?
We’re going to assume a somewhat basic familiarity with functional programming concepts and a basic understanding of monads (if you don’t know that much, check out adit’s great concice guide). If you aren’t familiar with MonadPlus/Alternative (and how they work as monads) check out Part 1 and Part 2, which should provide all the background and most of the syntax. Most Haskell syntax is either be explained here as we get to it or in the previous parts. Still, if you have any questions, feel free to leave a comment, give Learn You A Haskell a quick read, or stop by freenode’s friendly #haskell!
A MonadPlus Review
The usefulness of a monad depends on how you define the characteristic “bind” or “chaining” behavior. For this article, MonadPlus refers to the design pattern (and Haskell typeclass) where you model this “chaining” as a “success/fail” process1.
There is a common language with to talk about this process:
mzero means “fail here” and
return x means “succeed with a result of the value
x here”. So chaining is implemented such that chaining anything to a failure will propagate that failure forward. That is,
mzero >> return x =
So, armed with what we learned in Part 2, let’s formulate a general plan for finding all solutions in
Now, in the List monad, we can think of things as “journeys” or stories: subject your value to a long and arduous journey, specifying at every step of the way what choices it has to continue. Then specify where journeys fail and end. At the end of it all, the result is a list of the finishing values of all trails that have completed the journey.
With the List monad, we say “Here is the description of a (single) journey. What journeys following this description succeed?”
So what could this journey be for us? Well, we think of a journey in this situation as the accumulation of moves to a plan. We start out with a blank plan (“Do nothing”). The next step, we add one move to our plan (“Just move the fox”, for example). Then the next step, we add another move (“First move the fox, then move the farmer”).
- Start with a blank plan; a tabula rasa.
- Add a legal and safe move to it.
- Repeat Step 2
- Fail if you aren’t a solution; succeed if you are.
Simple, right? We just laid out the path of a single plan, from its birth to its eventual death or ascension.
This is the most significant thing about this approach: it allows you to describe one journey, in general terms, and List will “automatically” find out all successful journeys that fit your mold. You don’t ever have to worry about the ensemble or manually deal with explicit branching or filtering. Cognitively, all you have to do is write one story. Just one. That is the power of the List Monad abstraction.
The first thing we do when writing any Haskell program: define our types!
data Character = Farmer | Wolf | Goat | Cabbage -- 1 deriving (Show, Eq, Enum) newtype Move = MoveThe Character -- 2 deriving (Eq) instance Show Move where -- 3 show (MoveThe Farmer) = "F" show (MoveThe Wolf) = "W" show (MoveThe Goat) = "G" show (MoveThe Cabbage) = "C" type Plan = [Move] -- 4 data Position = West | East -- 5 deriving (Show, Eq)
- First, we define the enumerated type
Characterall the characters we will be working with: the farmer, the wolf, the goat, and the cabbage.
- Next, we define a simple
Movecontainer, which just contains a character. A
MoveThe Farmerwill represent a movement of only the farmer, a
MoveThe Wolfwill represent the movement of both the farmer and the wolf, etc.
- For the purposes of easy debugging, we’re going to define our own instance of
Showfor moves so that we can use
- A simple type synonym; a
Planis just a list of
Moves. Note that we are not using this list as a MonadPlus — it’s just a plain dumb list of moves in our plan.
Positiontype: either on the west bank or on the east bank of the river. Everyone starts out on the west bank, and we want them all to end up on the east bank.
Welcome to Haskell!
Hi! These “Welcome to Haskell” asides are for people unfamiliar with Haskell, mostly for Haskell syntax stuff. If you already feel comfortable, feel free to skip them.
There’s a lot of Haskell syntax and concepts here; mostly, all we are doing is declaring new types.
We declare that
Characteris “either” a
Cabbage. This is like saying that a
Boolis either a
True: in fact, you could define your own
Boolwith something like this: (or even your own
derivingsyntax tells the compiler to automatically derive functions for printing the type (Show), testing for equality (Eq), and enumerating through them (Enum)
We declare a new type
Movewhich is just a wrapper around a
Character. We can create a new
ghci>represents a command at the interactive prompt ghci, and
:tasks for the type of whatever comes after it)
Here we define custom functions for printing out a
Here is a type synonym
Plan. Every time we use
Planas a type, we really mean
[Move], and the compiler treats the two things as the same.
Position: same deal as
The Final Step
We’re going to skip to the end and write our final step and what it is supposed to be, and then fill in the functions that are necessary to make it happen.
The last stage of our journey is after we have made all
n moves, we end the journey if it is not a solution.
- The type signatures of the helper functions we will be using.
findSolutions nis going to be the all successful plans after
pbe a plan after
nmoves have been added to it. Note that
makeNMovesis itself a journey — a sub-journey. So
pis a single plan that has already gone through the
makeNMovesjourney. We are continuing that journey.
- End the journey unless
pis a solution (all characters are on the east side)
- Succeed with
pif the journey has not yet ended.
Hm. Sounds good! We’re done!
So now we only need to implement
Welcome to Haskell!
Haskell is a functional language…but that “do” block sure looks very imperative to me. What gives?
As explained in Part 1, all do blocks are just syntactical sugar for repeated applications of
makeNMoves is going to be the main logic of our program. We want it to be a journey, itself — a journey of a single plan going through
n additions of moves.
That means we want something like:
Which says “The journey of
makeNMoves is repeatedly making a move
Of course we have seen that particular type of
do block before, it is simply:
Luckily there is a function in the standard library that allows us to repeatedly apply a function
iterate :: (a -> a) -> a -> [a].
iterate f x takes a function
f :: a -> a and repeatedly applies it to a starting value
x :: a and yields the results as a list:
And so to get the
nth application, we use
iterate f x !! n (
!! being the indexing function, getting the
nth element of the list)
So now we can define
We say “apply
n times, starting the single starting plan”.
Welcome to Haskell!
return x >>= f is the same as
f x. You can see this here:
return x says “succeed with the value
y <- says “set
y to the value of that success”. Of course,
y is just going to be
x, because we had just said “succeed with the value of
x. That means that
f y is the same as
Even though the syntax is not the cleanest, it is important to remember here that what we are doing is simply defining the journey
makeNMoves as the result of taking
makeMove journeys one after the other. The same as that first do block.
Let’s define our helper function
isSolution :: Plan -> Bool. Basically, we want to check if the positions of all of the characters are
First, we need a way to get the position of a farmer/animal after a given plan has been executed.
positionOf :: Plan -> Character -> Position is going to take a
Plan and a
Character, and report what side of the river the character is on.
Because every single move swaps the position of the farmer, the final position of the farmer depends only on the even-/odd-ness of the number of total moves. If it is even, then the farmer is on the west bank still (consider 0 moves, two moves, etc.). If it is odd, then the farmer is on the east bank.
Now, what if we want to know about non-farmers?
Instead of finding the total number of moves, we only need to find the number of moves involving that given animal.
Let’s first filter the Plan
p by moves involving the character
This will return a new Plan, but with only the moves involving the character
c. We can then use the length of that.
Welcome to Haskell!
filter :: (a -> Bool) -> [a] -> [a] is a common function that takes a predicate
a -> Bool and a list, and returns a new list with only the items for which the predicate returns true.
(== MoveThe c) is a function that returns true if the move is equal to
Putting it all together:
Welcome to Haskell!
positionFromCount . length $ p?
In Haskell, the
(.) operator represents function composition.
(f . g) x is equivalent to
f (g x). “Apply
g first, then apply
Also recall that you can think of
$ as adding an implicit parentheses around both sides of it. You visualize it like the spine of a butterfly — the “wings” are wrapped parentheses around either side of it. In that sense,
f . g $ x is the same as
(f . g) (x) (A rather lopsided butterfly).
positionFromCount . length $ p is the same as
(positionFromCount . length) p, which says “first, find the length of
p, then turn that length into a position.”
In the same way,
positionFromCount . length $ filter (== MoveThe c) p is
(positionFromCount . length) (filter (== MoveThe c) p) — find the length of the filtered list, then turn that length into a position. We use
$ mostly because we don’t like writing parentheses everywhere when we don’t have to.
Does this actually work? Let’s try out some examples.
It works! By the way, as an unrelated note, isn’t it cool that our
Plan literal reads a lot like English? MoveThe Goat, MoveThe Farmer, MoveThe Wolf…
Checking the Path
Now we have to check that the plan is a solution.
Simple — that means that all
Characters are on the east side.
We can check this manually:
Hm. Rather ugly.
We see a common pattern that we need
positionOf p c for all
cs. That looks like a map!
We also compare all of them to
East. That sounds like a job for the prelude function
all :: (a -> Bool) -> [a] -> Bool, which takes a predicate and a list and returns true if all items in the list satisfy the predicate.
Let’s piece it all together:
Welcome to Haskell!
map is probably the most ubiquitous concept in functional programming — it takes a function and a list and returns a new list with the function applied to every item.
map f [x,y,z] =
[f x, f y, f z]. If we wanted to find the lengths of a list of strings, we’d do:
So in our case:
[Farmer ..] as shorthand for
[Farmer, Wolf, Goat, Cabbage] — this is because
Character is an Enum, so it can be enumerated using enumeration syntax. It basically means “
So let’s get down to the meat of our journey. How do we make a move?
makeMove will be a function that takes a plan and returns all the successful ways you can add a move to that plan. It takes a plan and takes it through a journey of adding a move, and returns the results of all of the successful ways it can fulfill this journey. This is similar to our old
halveOrDouble :: Int -> [Int], which takes an int and returns the successful paths our int could have taken (it could have been halved…or doubled).
What does a plan have to “go through” in its journey in adding a move?
- First, we get the move we want to add. We could pick a
MoveThe Farmer, a
MoveThe Goat, or anything!
- Then, we fail/end the journey if we pick a move that isn’t legal. For example, we can’t move the goat if the farmer is not on the same side of the river that the goat is on.
- Now, we add that move that we got to the plan.
- Then, we fail/end the journey if that new plan is “unsafe” — if it leaves either the Wolf and Goat alone on a riverbank or the Goat and Cabbage.
- At the end of it all, we succeed with the new plan.
Let’s try this out:
- Here are the types of the helper functions we will be using.
- In this context,
MoveThe <$>means to apply
MoveTheto whatever we choose out of
[Farmer .. Cabbage]. Kind of an “intercept it on the way out, and turn it into a Move”. So
MoveThe Wolf, etc.;
nextis one of those. For every journey, we pick one of the possible moves.
- We insta-fail if the move is not legal with the given plan. By this, we mean that we can’t possibly move an animal unless the farmer is on the same side as the animal.
- Let’s let
nextappended to the original plan
- We insta-fail unless the new plan is safe.
- If we haven’t failed yet, then we succeed with the new plan as the result.
Welcome to Haskell!
Okay, so I was slightly hand-wavey with
<$>. But it is true that something like:
will put 6 (
3 * 2) into
x — it’ll take out the 3 and then apply
(*2) to it before storing it in
What’s going on under the hood is actually less magical.
<$> basically says “apply inside”. It is like
$, but “inside”. Remember how we can do:
(*2) to 3? We can then also do:
Now, if we think of a List like a list of possible successes, then applying a function “inside” means applying the function to all of the possible successes:
So when I say
I really mean
But still, it sometimes is cool to think of it as “Get the item inside, and then apply this function to it before you bind it to your variable”, if only for funsies.
So let’s say our plan is, currently,
[MoveThe Goat, MoveThe Farmer, MoveThe Wolf]. At the end of it all, our goat, wolf, and farmer are on the east bank, and the cabbage is on the west bank.
What happens on a typical journey of
- First, we pick something to move. Let’s say
- This move is legal (moving the farmer is always legal).
- Our new plan is
[MoveThe Goat, MoveThe Farmer, MoveThe Wolf, MoveThe Farmer]
- This plan is not safe. If we move the farmer, the goat and the wolf will be alone, and that is bad news for the goat. We fail at the second guard.
- We don’t return anything, because this journey is a total and utter failure.
Huh. How unfortunate. Let’s try again with another pick for
- Let’s pick
MoveThe Cabbagethis time for
- This move isn’t even legal! The cabbage is on the west bank but the farmer is on the east. Failure!
Well, that’s kind of depressing. Let’s try another:
- We pick
- This move is legal; both the goat and the farmer are on the east bank.
- Our new plan is
[MoveThe Goat, MoveThe Farmer, MoveThe Wolf, MoveThe Goat].
- This plan is indeed safe. The goat and the cabbage are now on the west bank, but so is the farmer.
- Because all is well, we return our new plan!
As an exercise, see how the journey fares if we had picked
MoveThe Wolf for
Anyways, at the end of it all,
makeMove will return all new plans from the successful journeys. So it won’t be returning the plans with
MoveThe Farmer and
MoveThe Cabbage added to it, but will likely be retuning the plans with
MoveThe Goat and
MoveThe Wolf added to it. And it’ll return those two together in a List structure.
We’re almost there! Now to just define our helper predicates
What makes a move legal? Well, the farmer has to be on the same side as whatever is being moved.
We can re-use our
positionOf :: Plan -> Character -> Position function here.
One last piece. How can we tell if a plan is safe or not?
The plan is safe if nothing can eat anything else. That means if the wolf and goat or goat and cabbage sit on the same bank, so too must the farmer. Some boolean arithmetic will show that this is the same as if either the farmer is on the same side as the goat or the goat and cabbage are both “safe” (not on the side of their predators).
And…that’s it! We finished!
Notice that sometimes we are going to make “redundant moves”. For example, we could move the farmer or goat twice in a row. How can we add another guard to check if the move isn’t redundant? That is, that the move we are adding isn’t identical to the last move of the plan?
The implementation is in the final solution later on, but think about how you would do it and compare the final solution to yours!
The final code for this project is available on Github so you can follow along yourself. You can also load it interactively online on FPComplete, a great online Haskell IDE where you can test your code right there in the browser.
So…let’s test it!
First, let’s load it up on ghci:
Let’s try a few plan lengths and see when we get one that has a valid solution:
Great, we have two solutions of length 7. If we try them out, it seems like they both work! Notice that, interestingly enough, the two solutions are their own reverses. This makes sense, because any solution of getting from the west bank to the east bank must also be, backwards, a valid solution of getting from the east bank to the west bank.
It turns out that the solutions of length 9 and 11 are both identical to the solutions for length 7, just with some redundant moves thrown in (moving the farmer twice in a row, moving the goat twice in a row, etc.). Also, note that all possible solutions are of odd lengths, because for even lengths, the farmer ends up on the west bank.
If we add the filter on redundant moves mentioned earlier, the next valid solutions with no direct redundancies come at length 13, and then at 19:
Again note that both of these solutions come in pairs, with one being the reverse of the other. Also curious is the fact that they are actually identical to the length 7 solutions, just with cycles of
C,G,W) over and over again in the middle.
We have solved the classic logic puzzle without using any control flow other than the List’s MonadPlus instance. The solution isn’t necessarily optimal, but it is interesting that we can model something like this simply as saying: “Here is the description of a journey. What journeys following this description succeed?”
With the List MonadPlus, you can solve any problem that can be described as the result of a nondeterministic journey with choices and pitfalls along the way.
In this particular puzzle, you could have done something similar from the start using only maps and filters. However, sometimes it is more useful or more insightful to, instead of using maps and filters, use abstractions that help you frame the problem in a more meaningful way.
Hopefully as a result of this three part series and through playing around with the source code, you can appreciate the wonders of Succeed/Fail and MonadPlus!
Where to go from here? You might want to take a look at the Alternative typeclass/design pattern, which also deals with the concept of success/failure — just not with their consecutive chaining, like MonadPlus. It deals with their parallel choices, actually, as the name implies. This functionality is redundantly implemented in MonadPlus in Haskell today (2013), and the parallel-choice operator
<|> for Alternative is
mplus for MonadPlus. I might write something on the matter some day. Anyways, learning about Alternative will help you see more about the usefulness of the success/fail design pattern, and it might help you gain the perspective which much of the early Haskell implementors apparently lacked: not everything is a monad!
You might be aware that in the current Haskell standard library organization, the implementation of MonadPlus also provides separate functionality — the “Plus”. We won’t be focusing on this part, because it is commonly regarded that it is more of a characteristic of the Alternative typeclass/design pattern. For the purposes of this article, MonadPlus is essentially “MonadZero”, as it should have been.↩