span.kw { color: #007020; font-weight: bold; }
code > span.dt { color: #902000; }
code > span.dv { color: #40a070; }
code > span.bn { color: #40a070; }
code > span.fl { color: #40a070; }
code > span.ch { color: #4070a0; }
code > span.st { color: #4070a0; }
code > span.co { color: #60a0b0; font-style: italic; }
code > span.ot { color: #007020; }
code > span.al { color: #ff0000; font-weight: bold; }
code > span.fu { color: #06287e; }
code > span.er { color: #ff0000; font-weight: bold; }
]]>
This is my attempt at a solution to the fox/goose/corn problem in Haskell. It was inspired by Carin Meier’s Clojure Kata for the same problem, although it deviates from the approach. A better Haskell developer might significantly improve on my version. I didn’t find much use for the standard typeclasses in this, sadly. As a consequence, however, the code is relatively understandable from the perspective of a Clojure programmer with no Haskell experience.
I’ll explain each construct as we encounter it.
Preliminaries
First, we have the namespace declaration. Unlike Clojure, we need to declare any identifiers we export. Since we’re writing an executable, we export main just as we would in C.
module Main (main) whereData.Set exports a lot of things with the same names that Data.List exports, so it’s pretty common to import it qualified. It’s not strictly necessary for the code that follows, though.
import qualified Data.Set as S
import Data.List(unfoldr)
import Data.Foldable(Foldable,foldr,find)The equivalent of clojure.core is the Prelude. We hide Left and Right because we’ll be using our own concept using those identifiers. We hide foldr because the version in Data.Foldable is more general.
import Prelude hiding (Left, Right, foldr)The Haskell Prelude is actually kind of frustrating, in that it doesn’t show off the language in its full power. It’s heading in that direction, though. In particular, this particular problem is getting addressed soon. Some people opt out of the Prelude altogether and use an alternative.
Basic Data Types
We’re writing Haskell, so we should write some types down.
You’ll recognize the following declarations as being identical to Java enums. Ord means it’s orderable, which in turn means you can put it in a set (hash sets aren’t the default in Haskell), Eq means you can test for equality using it, which comes along for the ride with Ord, Show means you can print it. Haskell magically writes the code in deriving.
data Item = Fox | Goose | Corn | Me deriving (Ord, Eq, Show)
data Side = Left | RightWe’ll represent everything using only the representation of the right hand side. This has the nice property that the initial state is the empty set. So we’re travelling from the Left to the Right. If we’d used a list, some of the code below would be prettier than using a set, but I believe set is the correct representation since it’s fundamentally unordered. It’s worth considering how it would look in Clojure with Set.
This is a newtype. type would indicate a type alias (so State was exactly the same thing as S.Set Item.) A newtype can’t be mixed with a raw set (which is what a Clojure programmer would naturally do) and requires you to explicitly construct and deconstruct it from the set as necessary. This obviously has a cost in verbosity, but has no runtime overhead because it’s all optimised out. It’s especially useful if you’re dealing with two concepts wih the same type representation. In our case, State and History (defined later) could be very easily confused in Clojure.
newtype State = State (S.Set Item) deriving (Ord, Eq, Show)State of Play
We’ll need some way of mapping booleans to Left/Right. We’re adopting a convention that Left = True here, and we’ve named the function to help keep this straight. Note that we have two definitions. Each definition is a pattern match on the right hand side. Basically, you need this for two things: identifying the side you’re on, and the side you’re not on, so the Bool -> Side mapping makes sense.
toRight :: Bool -> Side
toRight True = Right
toRight False = LeftNow let’s figure out which side we’re on. Here we destructure State for the first time.
onRight :: State -> Bool
onRight (State s) = S.member Me sWe also need a function that tells you what is on which side.
\means “difference”. SinceData.Setis namespace qualified, so is the operator.- Sadly there’s no general type that subsumes sets and lists so there’s a
List.\and aSet.\and they don’t interoperate well
Coming up with a good type system for lists and list like things is regarded as an open problem in the Haskell world and they’re not prepared to take the kinds of compromises Clojure and Scala have made. (Consider, for instance, that mapping a set returns a list.) However, in practice that means that using different types of lists together or writing general list-like code is a pain I could have introduced my own abstraction, but seriously, what’s the point?
Again, we have two definitions. This is the first time we use a where clause. A where clause is similar to a postfix let clause. Note that we don’t need type declarations for non-top-level declarations.
Also, this is an arity-2 function. Only there’s no such thing in Haskell. Haskell, like most FP languages (and unlike Clojure) only ever has functions that take one parameter and return one. So what you’re really looking at here is a function that takes a Side and returns another function which takes a State that then returns a set of items. If you just don’t apply enough parameters, you get the partial application of the function. I’ve long since been an advocate of programming Clojure like this ever since I spent a couple of hours in F#’s company.
side :: Side -> State -> S.Set Item
side Left (State s) = everyone S.\ s
where everyone = S.fromList [Fox,Goose,Corn,Me]
side Right (State s) = sThe whole reason we’ve defined the operations above is this: after this point we’ll never destructure State again, just interact with the State functions we’ve already defined. The hope is that this enables us to think at a higher level about what we’re doing. (I’m not going to argue this point, but there’s plenty of people on the internet prepared to do so.)
Haskell! So We Can Be Safe!
Let’s figure out if a State is safe. Turns out the rules for whether or not you’re safe are pretty easy
- The attended side is always safe
- The unattended side is safe if only the Goose is there
- No other unattended Goose is safe
- Every other unattended side is safe
We’re using more Haskell features here.
.performs functional composition, so(toRight . not . onRight)is equivalent to(comp toRight not onRight).- We can have multiple definitions in a where clause.
- We can call a variable _ if we don’t care about its value.
- You can put a “guard” on a pattern match. I prefer to use guards and pattern matching over explicit branching primitives.
a $ b c dmeans the same asa (b c d). This prevents ridiculous paren buildup. Clojure has different ways of avoiding this, most obviously->.
safe :: State -> Bool
safe s = safeSide $ side unattendedSide s
where unattendedSide = (toRight . not . onRight) s
safeSide l | S.member Goose l = S.size l == 1
safeSide _ = TrueIn practice, the side function is only used within safe so we could have just stuck it into the where clause and saved some newtype book-keeping.
Moving the Boat
I’m not 100% happy with the readability of this next function, mostly because it’s quite long. Suggestions are welcome.
We need to find the next possible states. We’re mapping to set, because there’s no inherent ordering of the future states. You can do the same in Clojure. Unlike clojure, we need a separate map function, S.map rather than map. The good news is that it returns a set rather than a lazy list.
There is a general map function, fmap that will map anything to its correct container type (and more!) but we can’t use fmap here for technical reasons (for the curious, lookup: “Set is not a Functor in Haskell”).
Also, note that this is where we finally actually create a new State, and that we can just use State, the constructor, as a straight function that we can map over.
transitions :: State -> S.Set State
transitions state = S.map State $ S.insert moveBoat carry
where onRight = S.member Me $ side Right state
mySide = side (toRight onRight) stateThe move command is either a delete or an insert, depending on the direction of travel. In Clojure this would be (if onRight dissoc assoc)
move = if onRight
then S.delete
else S.insertThe list of items is the things that are on your side that aren’t you.
items = S.delete Me mySideEffectively, this next line just destructures State.
right = side Right stateWhatever else happens, you’re definitely moving youself Note that moveBoat is the State represented by just moving yourself.
moveBoat = move Me rightIf you choose to move an item, it’s a motion on top of moveBoat, not on top of s, since you’re also moving.
We’re using flip, which swaps the parameters of move. We could also have said moveItem x = move x moveBoat or something with lambdas (IMO, lambdas are rarely the most clear option, and in this code they’re never used.) Although you could write flip in Clojure, it really isn’t Clojure “style”, but definitely is Haskell style
moveItem = flip move moveBoatcarry is the set of states if you carry an item with you
carry = S.map moveItem itemsThere’s a huge number of different types in the preceding function, and no type declarations other than the top level. You can put more type declarations in that I have, but you can’t put in fewer and compile with -Wall (If you’re OK with warnings, you can throw away the top level type declarations some of the time, but there’s a lot of reasons that’s a bad idea.)
Desperately Seeking Solution
We’ll ignore the State type completely for a while and just talk in general about how you solve this kind of problem.
We need to think about how to represent a sequence of moves. Here we newtype List (List here is a good choice of type, since history is fundamentally ordered). History is stored backwards for convenience.
newtype History a = History [a] deriving (Eq, Ord)Let’s make history print the right way around though. To do this, we need to implement the Show typeclass by hand. (Typeclasses are a bit like interfaces, but behave very differently.)
=> is the first example in the code of a type restriction. Here we’re saying “If a is showable, then History of a is showable.” Then the implementation says “The way you show it is by taking the list, reversing it and then showing that.”
instance (Show a) => Show (History a) where
show (History l) = show $ reverse lHow are we’re going to find the solution? You want to use your transition function to construct a set of possible histories and then search that list for a solution. You could basically do this as a breadth-first or a depth-first search. A breadth-first search will have the advantage of finding the minimal solution. To avoid wasting time on cycles such as the boat just going backwards and forwards, we’ll keep track of what positions we’ve already generated.
So, how to we go from all combinations of 2 moves to all combinations of 3 moves? We define a data structure, Generation.
data Generation a = Generation {
previous :: S.Set a,
states :: S.Set (History a)
}In practice, we know that a will be State, but it’s generally good Haskell style to use the most general type possible. When you get the hang of it, this aids clarity, rather than impeding it. (See also: parametricity and theorems for free).
Generation is a record data type. Like Clojure, you can use previous and states as accessor functions. Unlike Clojure, these functions are strongly typed. That means you can’t have fields with the same name in different records (within the same file/namespace).
Working with Generations would be better if we used lenses, but lets stick to things in the base libraries.
Implementing the Search
We need to map the function that generates new states to a function that creates new Generations. In Clojure, we’d probably use reduce. In Haskell, we use foldr, which is pretty similar, modulo some laziness and argument order differences.
(a -> S.Set a)is a parameter that is a function.- We’re specifying that
aimplementsOrd, which we need to be able to put it into aSet. - Due to the wonders of partial application,
(a -> S.Set a) -> Generation a -> Generation ais exactly the same as(a -> S.Set a) -> (Generation a -> Generation a)
liftG :: (Ord a) => (a -> S.Set a) -> Generation a -> Generation a
liftG f t = foldr (stepG f) initial (states t)
where initial = Generation {
previous = (previous t),
states = S.empty
}Actually, I’ve skipped the most important bit of this: the step function. I could have inlined it, but it’s pretty complex I prefer to give it its own top level declaration, along with a semi-scary type signature.
stepG :: (Ord a) => (a -> S.Set a) -> History a -> Generation a -> Generation a
stepG f (History h@(s : _)) t = resultThe destructuring of History is a bit more complicated. Here we’re assigning h to the whole history, and s to the latest state in the history. Note that if History is empty, the pattern match won’t work. Clojure would just match it and put nil in s. Type safety is pretty cool here but it means we need a new pattern match for empty histories. Strictly speaking, they aren’t valid, but the way we defined the type they can happen. (If you’re seriously thinking you want a type system that can express “non-empty list” I have two answers for you: core.typed and Idris.) This is the point at which Haskell goes “Well, I’m trying to be a practical FP language, you know.”
where result = Generation {Add the new states into the list of known states.
previous = S.union (previous t) nextStates,Add the new histories into the current generation.
states = S.union (states t) (S.map newHistory nextStates)
}The next states are the states of the transition function minus the known states.
nextStates = f s S.\ (previous t)The newHistory function is interesting. Observe (: h). Now (x : xs) is the same as (cons x xs) in Clojure. (x :) would be (partial cons x) and (: xs) would be #(cons % xs). So (: h) is a function that takes a t and puts it in front of the existing list. This is operator section and works for all operators (you can define your own) except (- x) (which is special cased to unary minus).
Again, History is just an ordinary function, that wouldn’t have been needed if we’d done types instead of newtypes.
newHistory = History . (: h)Finally, to avoid compiler warnings, tell it what happens when History is empty. This case should never happen.
stepG _ _ t = Generation { previous = previous t, states = S.empty }The Under-Appreciated Unfold
So, now we’ve got a Generation to Generation function, how do we get the list of all possible histories? Well, we could always just write some recursive code, but like in Clojure, there’s functions that exemplify common recursion structures. In Clojure, iterate might be good choice here. In Haskell, there’s unfoldr.
The type declaration of iterate in Clojure would be iterate :: (a -> a) -> a -> [a].
In comparison, the type declaration of unfoldr is quite complex: unfoldr :: (b -> Maybe (a, b)) -> b -> [a].
You might be wondering why they’re so different. The short answer is that unfoldr is awesome. The key is the step function itself b -> Maybe (a,b). This says that it takes a b and returns either Nothing (nil) or Just a pair of a and b. (Did I mention one of the coolest things about Haskell? null/nil doesn’t exist.) The b gets passed to the next step, the a gets output. So unfoldr supports having an internal state and an external state. What happens if Nothing is returned? The list stops generating. Clojure expects you to then terminate the list in a separate step, an approach that seems simpler but falls down when you start to use things like the state monad.
So, our output a is going to be the set of states of the generation, while b is going to be the Generations themselves. We’ll return Nothing when there’s no states in the Generation.
iterations :: (Ord a) => a -> (a -> S.Set a) -> [S.Set (History a)]
iterations start f = unfoldr (forUnfoldr . (liftG f)) initial
where forUnfoldr t | S.null (states t) = Nothing
forUnfoldr t = Just ((states t),t)
initial = Generation {
previous = S.empty,
states = S.singleton $ History [start]
}So we just call unfoldr with a generation producing function using forUnfoldr to adapt it to fit.
We’ve done this using unfoldr, which has explicit state. Control.Monad.Loops exposes unfoldM which could be used with a state monad to achieve a similar effect.
Fun with Types
Let’s have some fun. We’ve got a list of sets that contains the solution. There’s a perfectly good function for finding an element in a a list called find (as an aside: there’s no such perfectly reasonable function in Clojure). Small catch: it takes a Foldable (in Clojure, a reducable). List is Foldable, Set is Foldable, but a list of sets of states iterates through the sets, not the states.
We’ll do some type magic and make it iterate through the states. (Thanks to Tony Morris for pointing me to a way to achieve this. Much more brain-bending stuff is available in Control.Compose)
newtype Compose g f a = O (g (f a))instance (Foldable f1, Foldable f2) => Foldable (Compose f1 f2) where
foldr f start (O list) = foldr g start list
where g = flip $ foldr fSo, here we’ve said that a foldable of a foldable of a can be used as a single foldable by using flip $ foldr f as the step function. We could have just written this function out, but hey, why not live a litte.
The Finish Line
Finally, we get to main. Often this is expressed in do notation, but I don’t feel the need here, since it’s literally one line: print solution.
main :: IO ()
main = print solution
where solution = find success (O allHistories)
success (History (s : _)) = side Left s == S.empty
success _ = False
allHistories = iterations allOnLeft next
allOnLeft = State S.empty
next = S.filter safe . transitionsSo, you can build it, and run it. time reports that it takes 2ms on my machine. How on earth did it run so fast? Aren’t fully lazy functional languages meant to be slow? Well, there are advantages to running an optimizing compiler, but they’re helped by understanding a bit of what is going on under the hood. An unfold followed by a fold is called a hylomorphism. The thing is, you never need to build the whole structure, you could just run each iteration through the fold as it comes. The Haskell compiler is smart enough that it actually rewrites the code. So a large chunk of our code is actually running imperatively.
How much have types helped me write this code? Well, the early functions, especially safe, I needed to nail in GHCi, the Haskell REPL. On the other hand, the later parts of the code actually worked first time (after I’d managed to fix all of the type errors.). Make of that what you will.
I hope you’ve found this interesting. I’m still very much a beginner Haskell programmer, but I hope the presentation enables you to see how you can express ideas in Haskell. If you’d like to learn more, I can highly recommend starting with Brent Yorgey’s course.
Colour Coding 