text: span; }
  ]]>
  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) where
  Data.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 | Right
  We’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 = Left
  Now 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 s
  We also need a function that tells you what is on which side.
  \means “difference”. Since
  Data.Setis namespace qualified, so is the operator.
  - Sadly there’s no general type that subsumes sets and lists so there’s a
  List.\and a
  Set.\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) = s
  The 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 as
  a (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 _ = True
  In 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) state
  The
  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.insert
  The list of items is the things that are on your side that aren’t you.
  items = S.delete Me mySide
  Effectively, this next line just destructures
  State.
  right = side Right state
  Whatever else happens, you’re definitely moving youself Note that
  moveBoat is the
  State represented by just moving yourself.
  moveBoat = move Me right
  If 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 moveBoat
  carry is the set of states if you carry an item with you
  carry = S.map moveItem items
  There’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 l
  How 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
  aimplements
  Ord, which we need to be able to put it into a
  Set.
  - 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 = result
  The 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 f
  So, 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 . transitions
  So, 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.