# Clojure's Short Circuit Reduce in Haskell

Clojure's `reduce` has a feature its users are quite fond of: the ability to short-circuit evaluate using the `reduced` function. Here I'm going to reconstruct this behaviour from scratch in Haskell, and then show it's built into Haskell's fundamental abstractions.

`reduced` works by wrapping the return value. The `reduce` function specially detects this type and unwraps it before returning the value.

The declaration of `foldr` in Haskell is as follows:

``foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b``

(At least that's the sensible definition, but let's not go there.)

Here, `b` is the accumulator value, the initial value and the return value. Since we want to represent the value that may or may not be a short circuit value, let's use `Either`.

``foldr2 :: Foldable t => (a -> b -> Either b b) -> b -> t a -> b``

We're assuming `Left` is the short circuit value, and `Right` is a normal accumulator value. Let's say we're building `foldr2` using foldr. If we substituted `Either b b` for `b` we'd get the following:

``foldr' :: Foldable t => (a -> Either b b -> Either b b) -> Either b b -> t a -> Either b b``

We need to figure out how to take the inputs of `foldr2` and turn them into the inputs of `foldr'` (which are actually just the inputs of `foldr`).

`Either` is a monad. Don't worry, I'm not about to explain what a monad is. I'm just going to tell you. `Either` being a monad means there's two functions, `pure` and `=<<` (the second of which I wish had a name).

``````pure :: (Monad m) => a -> m a
=<< :: (Monad m) => (a -> m b) -> (m a -> m b)``````

or, in the case of `Either a a`

``pure :: a -> Either a a``

which is actually just the `Right` constructor

``=<< :: (a -> Either c b) -> (Either c a -> Either c b)``

which just means "map the right side but not the left". (Usually Haskell doesn't show the brackets on the right, I think it's more clear for our purposes though.)

## Resolving the Reduction Function

So, how can we use this to solve our problem?

``reduceFunction :: (a -> b -> Either b b) -> (a -> Either b b -> Either b b)``

Let's put some more brackets in it:

``reduceFunction :: (a -> (b -> Either b b)) -> (a -> (Either b b -> Either b b))``

Interesting, the bits in brackets are just the `=<<` function.

``````reduceFunction :: (a -> b -> Either b b) -> a -> Either b b -> Either b b
reduceFunction rf a b = (=<<) (rf a) b``````

So we partially applied the original reduction function with the first argument, then applied `=<<` to promote it to `Either b b -> Either b b`.

Let's apply a little trick: if you add a `.` to a function, you can take the last expression in the next bracket outside of the bracket (in paredit talk, a barf).

``reduceFunction rf a b = ((=<<) .) (rf) a b``

or, in fact

``reduceFunction rf = (=<<) . rf``

## Finishing Off The Details

If we now need to make the initial value an `Either b b`. That's easy, that's the other `Monad` function: `pure`. Finally, we need to extract the value out at the end

``````extract :: Either b b -> b
extract = either id id``````

`either` is a function that takes two extraction functions that return the same type and applies the correct one. In our case, we just use the identity function on both sides.

``````foldr2 :: (Foldable t) => (a -> b -> Either b b) -> b -> t a -> b
foldr2 rf i l = extract \$ foldr (reduceFunction rf) (pure i) l``````

I'm sure I've mentioned `\$` before, but it just means "put brackets around everything after this point". With some trickery (actually, just the trick I described before, applied multiple times) we can turn that into

``````foldr3 :: (Foldable t) => (a -> b -> Either b b) -> b -> t a -> b
foldr3 rf i = extract . (foldr ((=<<) . rf) . pure) i``````

Let's do a quick test as well

``````sumOdd :: (Integral a) => a -> a -> Either a a
sumOdd x y = if' (odd x) (Right \$ x + y) (Left y)``````
``````result :: Int
result = foldr9 sumOdd 0 [1, 3, 5, 6, 2, 3, 5]``````

Note that this gives us the sum of odd numbers from the right, not the left. This is the natural thing in Haskell, but completely crazy in Clojure. Strictly speaking, we should have been working on `fold'` in the first place.

## Dubious Extraction

We've established that we can implement Clojure's `reduce` abstraction. But if we take a look at our solution, only `extract` actually relies on it being an `Either`. So, if we threw that away we'd have

``````foldr3' :: (Foldable t) => (a -> b -> Either b b) -> b -> t a -> Either b b
foldr3' rf i = (foldr ((=<<) . rf) . pure) i``````

Now we're returning the still wrapped value, but we're only using functions that depend on `Monad`. So, we could have the type signature a lot more general without changing the code:

``foldr4 :: (Foldable t, Monad m) => (a -> b -> m b) -> b -> t a -> m b``

That looks pretty general. What happens if `m` is a `Maybe`? Then you get something that short circuits on `nil`. If `m` is `List` you get something that keeps expanding a list, like how we solved the Fox Goose Corn problem. I have no idea what it does for `State` and `Reader`, but it's probably useful.

Let's hoogle it.

``foldrM :: (Foldable t, Monad m) => (a -> b -> m b) -> b -> t a -> m b``

Oh, the function already exists (with a very different implementation, but it's functionally identical to what we did above).

So, our final version should probably just use that:

``````foldr5 :: (Foldable t) => (a -> b -> Either b b) -> b -> t a -> b
foldr5 rf initial list = extract \$ foldrM rf initial list``````

# Writing My First compdata Code

I've been trying to square a rather nasty circle in Haskell for some time, one that could be summarized as "How to do polymorphism". Try as I might, existential types didn't really work for me. They're great in their place, but it turned out that I kept needing to know the exact types just after I'd erased them. Then you have to throw explicit casts at them. It's worth noting that OO languages have the exact same problem: everything's polymorphic by default, but actually you've got to cast the type half the time anyway.

I also tried using HList, but the truth is that it's a solution that's a pain to use (because you have to prove all the types), and really challenging to use if you're a beginner. This is a pity, because it's an obviously powerful idea that can generate ridiculously optimal code, but I don't know how the usability could ever be improved.

For those not familiar with my previous posts, the basic problem I'm trying to code is the ability to represent expressions and simplify them.

For a while, I was starting to think there was no solution which could be expanded and only a closed-type solution would do the trick, but Data types a la carte showed me another model, which uses what are strictly speaking closed types, but ones that can be flexibly created.

The original text is pretty readable, but leaves out one rather important detail: you've got to do a fair bit of engineering to make it efficient in Haskell. This is where compdata comes in: it implements the ideas for you. The catch is that it goes beyond the original paper and is hard to navigate as a consequence. This post is just about how to get started using it.

## The Holy Grail

``````class Testable v a where
test :: a -> v -> Bool``````
``````class (Invertable a) => Analyzable a where
analyze :: a -> a -> ConditionRelationship``````

`Invertable` and other types here are the same as my last post.

``````class (Analyzable a, Analyzable b) => CrossAnalyze a b where
crossAnalyze :: a -> b -> ConditionRelationship``````

You'll note that, really, `Analyzable` and `CrossAnalyze` could be the same typeclass. Right now I'm finding it more convenient to put them together like this. I could always make it more flexible if I needed it.

Now for some things that are going to be instances of those type classes:

``data Always e = Always Bool deriving (Eq, Show, Typeable)``
``````data ValueC c v e = Value {
_condition :: c,
_value :: v
} deriving (Typeable, Eq, Show)``````

These definitions are a bit different from last time, so let's talk through them:

• `c` is the type of the condition
• `v` is the value to be compared

`e` is more complex. We're planning to stick Always and ValueC into the same type. That type will be called `ConditionY`. `e` will then be `ConditionY v`. This type parameter is needed to allow us to add `And` and `Or`, but we won't be doing so in this post. For our purposes, the point is that we parameterize our base types by a free type that is ultimately going to be our intended type.

So, let's see our intended type:

``type ConditionY' v = Always :+: ValueC Equality v :+: ValueC Comparison v``
``type ConditionY v = Term (ConditionY' v)``

## And Now For Something Completely Different

Now, it's easy enough to make the types `Always` and `ValueC` testable, but how do we make the type sum of them tesable? It's a two stage process:

``````instance (Testable v (f e), Testable v (g e)) => Testable v ((f :+: g) e) where
test = caseF test test``````

`caseF` is a useful function that says "call the left if it's an `f`, call the right if it's a `g`". In this case, the first `test` belongs to the typeclass instance for `f`, and the second for `g`.

Haskell can apply this rule multiple times to deduce that, since all the components of `ConditionY' v` are testable (strictly speaking, can be used to test `v`s), so is `ConditionY' v`.
Now we perform a bit of sleight of hand. If `(ConditionY' v e)` is tesable, a special case of that is `ConditionY' v (Term (ConditionY' v) e)`. If we call `ConditionY' v` `f` then that's `f (Term f)`. But that can be converted to and from `Term f` like a newtype using `unTerm` and `Term`.

``````instance (Testable v (f (Term f))) => Testable v (Term f) where
test = test . unTerm``````

Remembering that we defined `f` to be `ConditionY' v`, we have now made `ConditionY v` an instance of `Testable` for `v`.

## Life of Brian

We can now do the same for `Invertable`

``````instance (Invertable (f e), Invertable (g e)) => Invertable ((f :+: g) e) where
invert (Inl x) = (Inl (invert x)) :: (f :+: g) e
invert (Inr x) = (Inr (invert x)) :: (f :+: g) e``````

We couldn't usefully use `caseF` here because directing the types back to the original is pretty painful, so instead we've used the `Inl` and `Inr` constructors directly. Finishing the process just involves promoting the operation to the `Term` level.

``````instance (Invertable (f (Term f))) => Invertable (Term f) where
invert = Term . invert . unTerm``````

We can now use CrossAnalyze to provide an Analyzable for the type sum:

``````instance CrossAnalyze (a e) (b e) => Analyzable ((a :+: b) e) where
analyze (Inl x) (Inl y) = analyze x y
analyze (Inr x) (Inr y) = analyze x y
analyze (Inl x) (Inr y) = crossAnalyze x y
analyze (Inr x) (Inl y) = invert \$ crossAnalyze y x``````

Note that the order that we declare the terms in the sum has to be consistent with the direction we declare `CrossAnalyze` in. If we just allow `CrossAnalyze` in both directions, all we succeed in doing is confusing the compiler.

``````instance (Analyzable (f (Term f))) => Analyzable (Term f) where
analyze = on analyze unTerm``````

`on` remains one of my favourite Haskell functions that has no analogue in other languages.

## The Meaning of Life

Now, I've already developed an extensive set of tests for the `analyze` function, so it's now just a matter of figuring out how to plug into them. The biggest issue is how to create values of these rather complex types. Luckily, compdata doesn't the heavy lifting for us.

``````\$(derive [makeFunctor, makeTraversable, makeFoldable,
makeEqF, makeShowF, smartConstructors, smartAConstructors,
makeArbitrary, makeArbitraryF]
[''ValueC, ''Always])``````

This has actually done a lot more work than I've covered here, but my purposes, what it has done is create `iValueC` and `iAlways`, which can be used to create `ConditionY`s. The small catch is that they can be used to create all sorts of other things to, so we need to specify the target type. So you end up writing stuff like `(iAlways True :: ConditionY Int)` and, even worse `(iValue Eql (3 :: Int) :: ConditionY Int)`. There is, of course, nothing stopping you from aliasing these functions with a more constrained type for your own purposes.

Next, I'm going to extending the expression language to `and`, `or` and projections. I think this solution finally allows me to express these concepts flexibly without trashing the types.

Last time, I was looking into establishing equality on various conditions on `Wai.Request`, but established that this wasn't what I was looking for. We did, however, establish how to perform casts and use polymorphic lists in a fashion that's quite OO. Now I'm planning to drive right off road and try a bit of type-level reasoning.

Let's start by simplifying the problem we had last time. Let's stoop worrying about complex record types and just deal with primitive types. We'll restrict our attention to equality and comparison conditions on those types. Let's start by setting up some machinery.

``data Equality = Eql | NEql deriving (Show, Ord, Eq, Typeable)``
``````equalityAsFunc :: (Eq a) => Equality -> a -> a -> Bool
equalityAsFunc Eql = (==) equalityAsFunc NEql = (/=)``````
``data Comparison = LTh | LThE | GThE | GTh deriving (Show, Eq, Ord, Typeable)``
``````comparisonAsFunc :: (Ord a) => Comparison -> a -> a -> Bool
comparisonAsFunc LTh = (<)
comparisonAsFunc LThE = (<=)
comparisonAsFunc GTh = (>)
comparisonAsFunc GThE = (>=)``````
``````class Invertable a where
invert :: a -> a``````
``````instance Invertable Comparison where
invert LTh = GThE
invert GTh = LThE
invert GThE = LTh
invert LThE = GTh``````
``````instance Invertable Equality where
invert Eql = NEql
invert NEql = Eql``````
``````-- I could make all functors of a invertable invertable, but I'm not sure that would actually be a good idea.
instance (Invertable a) => Invertable (Maybe a) where
invert = fmap invert``````
``````-- Util
infixl 3 <|!> (<|!>) :: Maybe a -> a -> a
(<|!>) = flip fromMaybe``````

Now, we're going to have a Condition typeclass, and at the very least we're going to have instances for "always true/false", "test for equality/inequality" and "compare against value". And here's the important bit: we're going to want to analyze the relationship between them, even if they're not the same type.

``data ConditionRelationship = Same | Compatible | Incompatible | AImpliesB | BImpliesA deriving (Show, Ord, Eq, Typeable)``
``````instance Invertable ConditionRelationship where
invert AImpliesB = ImpliesA
invert BImpliesA = AImpliesB
invert x = x``````

## Young Rankenstein

Now, how would we achieve this in an OO world? Well, we'd implement something like this:

``````class Condition0 c where
analyze = (Condition0 d) => c -> d -> Maybe ConditionRelatioship``````

Where we'd return `Nothing` if `c` didn't know how to analyze its relationship with `d`. Using the `cast` mechanism we've already seen, you can definitely implement this. And indeed, I did. (I tried an approach involving a more symmetric approach and some type magic, but ultimately couldn't get it to fly.)

Let's revise the definition a little so that we can actually it to test values. But we're going to have to introduce a second type, `v`, the value under test.

``````{-# LANGUAGE RankNTypes #-}
class Condition1 v a where
analyzeSame :: a -> a -> ConditionRelationship
analyzeDifferent :: (Condition1 v b) => a -> b -> Maybe ConditionRelationship
test :: a -> v -> Bool``````
``````analyze :: (Condition1 v a, Condition1 v b) => a -> b -> ConditionRelationship
analyze x y = a <|> b <|> c <|!> Compatible
-- If we have no idea, say it's compatible
where a = analyzeSame x <\$> (cast y)
b = analyzeDifferent x y
c = invert \$ analyzeDifferent y x``````

Now, there's actually a serious problem with this code: it doesn't even compile! The problem is with the `v`s in `analyze`. It can't determine that they're the same. This I actually find weird, given that I've specified that `a` and `b` share a `v`, but it's solvable.

First, I want to talk a bit about what the rank 2 typeclass actually is. It specifies a set of functions that can be called with an `a` and a `v`, but doesn't restrict the `a` or the `v` in any way. So, all it's really giving you is a relationship between the two types. And `analyze` never uses `v`, so it can't deduce anything about it.

Now, there's an extension called `FunctionalDependencies` and another called `TypeFamilies` that'd resolve this, but actually all we need to do is take the `test` method back out.

``````class (Eq a, Show a, Typeable a, Invertable a) => Condition2 a where
analyzeSame2 :: a -> a -> ConditionRelationship
analyzeDifferent2 :: (Condition2 b) => a -> b -> Maybe ConditionRelationship``````
``````class (Condition2 a) => Condition3 v a where
test :: a -> v -> Bool``````
``````analyze2 :: (Condition2 a, Condition2 b) => a -> b -> ConditionRelationship
analyze2 x y = a <|> b <|> c <|!> Compatible -- We have no idea, say it's compatible
where a = analyzeSame2 x <\$> (cast y)
b = analyzeDifferent2 x y
c = invert \$ analyzeDifferent2 y x``````

That works, doesn't use any more extensions, (although Lord knows I've been playing extension pokemon recently) and also leaves us with the possibility of using different `v`s with the same `a`, even if in this particular case I can't see why we'd wish to. For that matter, we could remove the interdependency between the two.

``````class Condition4 v a where
test :: a -> v -> Bool``````

I found it really interesting the process I went through here: we actually ended up with a better design and separated our concerns as a consequence of the type system complaining about the functions we actually implemented.

## Into The Lens

Let's rename our concepts:

``````class (Eq a, Show a, Typeable a, Invertable a) => Analyzable a where
analyzeSame :: a -> a -> ConditionRelationship
analyzeDifferent :: (Analyzable b) => a -> b -> Maybe ConditionRelationship``````
``````class Testable v a where
test :: a -> v -> Bool``````

First some definitions:

``````data Value c v = Value {
_value :: v,
_condition :: c
} deriving (Typeable, Eq, Show)``````
``makeLenses ''Value``
``````instance (Invertable c) => Invertable (Value c v) where
invert = over condition invert``````

I'm using the `lens` package here, although to be honest I'm really only using it to start learning it. The actual practical benefits of it in the code I've written are very small, but I'm hoping to slowly pick up more aspects. In fact, of the code I've written so far this is the only bit that actually shows an improvement.

Breaking it down, we're saying that if a `condition` is invertable, a `Value` using that `condition` is invertable by inverting the `condition`. Even though this is pretty elegant, but it's going to take me a fair while to get my head around lens in general (There's been loose talk of a lens NICTA-style course, that would be awesome.).

## Scopes Monkey

So, we can declare an equality value to be a condition:

``instance (Typeable a, Show a, Eq a) => Condition a (Value Equality a) where``

I'm deliberately skipping the instance code because it's pretty boring and predictable. The interesting case is when we're implementing comparison:

``analyzeEqualOther :: (Invertable b, Testable v b) => b -> Equal v -> ConditionRelationship``

(I'll skip the implementation.) Now for an instance:

``````instance (Typeable a, Show a, Ord a) => Analyzable (Value Comparison a) where
analyzeSame = analyzeCompSame -- elided
analyzeDifferent x y = analyzeEqualOther x <\$> y2
where y2 = cast y``````

Makes sense. Doesn't compile. The reason's a bit weird: it can't figure out exactly what to cast `y` to. So let's try this:

``    where y2 = (cast y :: Maybe (Value Equality a))``

Still doesn't work. Here, the error message isn't particularly helpful (unlike quite a few that just point you directly to the extension that you might need). The problem is actually that the `a` in the `y2` expression isn't the same as the `a` in the instance declaration. I don't really understand why that decision was made (the explanation probably features the word "parametricity"), but you can reverse it by adding in another extension:

``{-# LANGUAGE ScopedTypeVariables #-}``

## QuickCheck Yourself

There's a plethora of things we could test, but let's start with this one: What actually is the relationship between the `Analyzeable` version of condition and the `Testable` version of condition? Well, the answer is approximately that given two types that are both, we should be able to pick a set of `v`s such that we can deduce the behaviour of one from the other.

It would be lovely if we could achieve this through the type system, but I think that would be a serious reach, and even if it was possible it's doubtful it would be readable. So instead let's try using QuickCheck, the original property testing tool.

Aside: conversely, there should be no value of `v` where the behaviour of the two contradict one another. However, this latter condition is kind of hard to demonstrate using any example-based system. For that, you really do want Idris.

We need to set up some infrastructure to make cabal run tests.

``````Test-suite test
Type:              exitcode-stdio-1.0
Hs-source-dirs:    test
Main-is:           Main.hs
Build-depends:     base >=4.7 && <4.8,
tasty,
tasty-quickcheck,
derive,
QuickCheck,
myprojectname``````

This introduces a new target called `test`. I've not used quickcheck before so this is quite interesting. `tasty` appears to be the standard test running infrastructure. Note that since the test code is actually a separate executable, you need to put your own code as a dependency.

## Stuck In The Middle With You

So, let's pick five distinct values, `a`, `b`, `c`, `d` and `e`. We'll put conditions at `b` and `d` and then test all five values in pairs. We can then read out from the set of pairs what the correct relationships between the two conditions is.

``````import Test.QuickCheck

data TestValues x = TestValues {
a :: x,
b :: x,
c :: x,
d :: x,
e :: x
} deriving (Show, Eq, Ord)

instance (Arbitrary a, Ord a, Num a) => Arbitrary (TestValues a) where
arbitrary = do
a <- getPositive <\$> arbitrary
b <- (a +) <\$> getPositive <\$> arbitrary
c <- (b +) <\$> getPositive <\$> arbitrary
d <- (c +) <\$> getPositive <\$> arbitrary
e <- (d +) <\$> getPositive <\$> arbitrary
return (TestValues a b c d e)``````

This is all rather fun: `arbitrary` returns a value in the `Gen` monad. `getPositive` unwraps a `Positive` and return type polymorphism kicks in.

Normally, though, how to create an `Arbitrary` instance is obvious given its components, setting them up is going to get boring real fast, which is where the `derive` package kicks in

``````{-# LANGUAGE TemplateHaskell #-}
import Data.DeriveTH

derive makeArbitrary ''Equality
derive makeArbitrary ''Comparison
derive makeArbitrary ''Value``````

This now enables us to write the code we wanted:

``````propDeduce :: (Analyzable (Value c1 v), R.Testable v (Value c1 v), Analyzable (Value c2 v), R.Testable v (Value c2 v))
=> c1 -> c2 -> TestValues v -> Bool
propDeduce c1 c2 testValues = expected == drawConclusion x y testValues where
x = Value c1 (b testValues)
y = Value c2 (d testValues)
expected = analyze x y

drawResults :: (R.Testable v (Value c1 v), R.Testable v (Value c2 v))
=> (Value c1 v) -> (Value c2 v) -> TestValues v -> [(Bool,Bool)]
drawResults x y testValues = result where
result = f <\$> ([a, b, c, d, e] <*> (pure testValues))
f v = (test x v, test y v)

drawConclusion :: (R.Testable v (Value c1 v), R.Testable v (Value c2 v))
=> (Value c1 v) -> (Value c2 v) -> TestValues v -> ConditionRelationship
drawConclusion x y testValues = ac (length conclusions) conclusions where
conclusions = nub \$ drawResults x y testValues
ac 4 _ = Compatible
ac 3 _ = ac3 missingConclusion
ac _ x | null \$ x \\ [(True,True),(False,False)] = Same
ac _ _ = Incompatible
missingConclusion = head \$ [(True, True),(True, False),(False, True),(False,False)] \\ conclusions
ac3 (False, True) = BImpliesA
ac3 (True, False) = AImpliesB
ac3 (True, True) = Incompatible
ac3 _ = Compatible``````

You can now write quickcheck properties like

``````prop_deduceCompEq :: Comparison -> Equality -> TestValues Int -> Bool
prop_deduceCompEq = propDeduce``````

(There may be a better way of instantiating propDeduce with different types, but this definitely works.)

In practice, what now happens is you spend a large amount of time actually fixing your code and your tests. What you're seeing above is the output of that process. I learned a few things in the process.

• Although QuickCheck is good at telling you there's a problem, it's got no facilities at all for telling you why.
• Having relatively complex types makes it quite hard to reproduce a test in the repl. Conceivably the tooling for this could be improved.
• You need to split your code up into chunks that are testable in the repl. This is a lesson Clojure taught me as well, but having access to an excellent debugger in other languages keeps unteaching it.

This is getting really long: I've skipped over the entire tasty `code` and the entire implementation.

## Review

So the `Condition` design looks more appropriate to the aim of actually allowing us to optimize our tests, and Haskell's led us to a typeclass design better than the original item. There are, however, certain problems. For instance, the design I've outlined here is incapable of spotting that "> 2" is the same as ">= 3" in the `Integer` domain. Pretty much the only good solution to this is to require stronger conditions than just `Eq` and `Ord` for condition values, which allow you to perform these analyses. I'm not very inclined to do that, but this problem doesn't ruin my intended use. However, it highlights again just how challenging it is to write something truly polymorphic and correct.

It's pretty easy to see how you can extend this into projections as well. However, in practice it gets pretty tricky, because you need to do an order 2 cast. Thankfully, I got a good answer on StackOverflow of exactly how to achieve that. Separating out the concept of the condition from the projection also seems like a strong idea. Ultimately, though, I don't really like the way this is going. Casts work, and `Maybe` makes them safe, but the design feels like I'm circumventing the type system rather than using it.

TL;DR I continue trying to implement a routing library, but instead end up learning about `Typeable`, writing about orphan instances, reading and (so far) failing to understand type-magic and sending my first Haskell PR.

I remember when I was starting Clojure, one of the big catchphrases was that everything was opt in. A type system, inheritance, multiple dispatch, &c. On the other hand, there were actually plenty of things that weren't opt-in: Java itself, polymorphism, reflection and so on.

Haskell is another opt-in language. The basic type system and language is a requisite, but there's still a phenomenal number of things to opt into. Equality is opt in, `Hashable` is opt in, as we saw in the previous article, polymorphism through existential types is opt-in. Next, we're going to see "opt-in" type casts, and hopefully you'll see how they're better than what you can achieve in Java or C#.

``````{-# LANGUAGE TypeSynonymInstances #-}
{-# LANGUAGE FlexibleInstances #-}
``````import qualified Network.Wai as Wai
import qualified Network.HTTP.Types as H``````

So, the question I asked last time was, how can I tell if two `RequestConditionBox`s are equal? To do that, we're going to want to make `RequestCondition`s themselves implement equality.

(As an aside: the whole of the functionality of the last post might have been better implemented using good old functions or possibly the reader monad. However, I always wanted the conditions to be instances of `Eq` and `Show`. That's not going to be possible with that approach.)

``````class (Show rc, Eq rc) => RequestCondition rc where
isMatch :: Wai.Request -> rc -> Bool``````
``````data RequestConditionBox where
RC :: (RequestCondition rc) => rc -> RequestConditionBox
deriving (Show)``````

Oops, that isn't going to work: you can't derive `Show` on a GADT. So delete it. We'll need to implement `Eq` and `Show` for `RequestConditionBox`. (I'm going to skip `Show`.)

``````instance Eq RequestConditionBox where
(==) (RC a) (RC b) = a == b``````

Small problem: `a` and `b` are different types. And `Eq` only allows you to test that two members of the same type are equal. We need some way of checking that the two types are equal. Now, you can test for type equality in a type precondition but I can't see how I could make that work. We need something more like

``testEqual :: (Eq a, Eq b) => a -> b -> Bool``

Only right now we have no idea how to implement it.

## He's My `Typeable`

George Pollard pointed me to an experimental class called `Typeable`. As I alluded to earlier, it's opt-in, although I think the opt-in nature is more to do with the fact that it's not standardized yet than that there are types that can't logically have a typeclass instance.

`Typeable` looks like a pretty unpromising typeclass:

``typeRep# :: Proxy# a -> TypeRep``

Actually, it's more than just unpromising, it looks positively hostile. What are those hashes? Well, it turns out that hash is a valid character in an identifier if you enable the MagicHash extension. As a convention, GHC uses it to represent unboxed types. Unboxed means exactly the same thing as it does in C# and Java: something that doesn't have a garbage collected pointer around it. This is a very deep rabbit-hole that I'm just going to carefully step around right now.

Actually, I'm going to skip pretty much everything except to notice that `Data.Typeable` exports a rather useful function called `cast`.

``cast :: (Typeable a, Typeable b) => a -> Maybe b``

Yep, that's exactly what `as` does in C#. I'll skip over the implementation, because it's slightly scary and I'd need to get into `unsafeCoerce`. One thing I can't tell is if this code is actually run at runtime or whether it's possible for the compiler to optimize it out. After all, the types of `a` and `b` are known at compile time.

With that, we can actually test if two values of different types are equal:

``````testEqual :: (Typeable a, Eq a, Typeable b, Eq b) => a -> b -> Bool
testEqual x y = fromMaybe False \$ (== x) <\$> cast y``````

• cast y
• map (`<\$>`) the maybe with `(== x)`
• this gives us `Nothing` if `x` and `y` are different types, and `Just (x==y)` if they're the same.
• finally, we use `fromMaybe` to strip off the `Just` and replace `Nothing` with `False`

## Orphan Black

To use `testEqual`, we need to make our `RequestCondition`s typeable

``````class (Typeable rc, Show rc, Eq rc) => RequestCondition rc where
isMatch :: W.Request -> rc -> Bool``````

How do we implement it? Well, we don't. `Typeable` is special. Not only is it derivable, the compiler requires you use the deriving version. And that needs an extension:

``````-- Put this up at the top
{-# LANGUAGE DeriveDataTypeable #-}``````
``newtype And rc = And [rc] deriving Typeable``

Unfortunately, `H.HttpVersion` doesn't implement `Typeable`. Luckily we can implement it ourselves. But, you guessed it, we need another extension:

``````-- Put this up at the top
{-# LANGUAGE StandaloneDeriving #-}``````
``deriving instance Typeable H.HttpVersion``

We're probably alright here, but what we've done is, in general, ridiculously dangerous. We've implemented an instance in a library that is neither the library that declares the typeclass, nor the library that declares the type. This is known as an orphan instance and will have seasoned Haskellers gathering with torches and pitchforks around your codebase. The reason for this is that, while typeclasses provide the power of ruby's mixins, orphan instances provide the problems. (They call it "incoherence", and they mean it.)

While we're on the subject, you'll probably have already noticed that when you add projects into your cabal file, you pull in the world, Maven style. This is pretty horrific, but the reason for this is orphan instances. For instance, the functionality of the `semigroups` package looks pretty small: it just exposes a couple of typeclasses. But when you take a look at what is an instance just of `Semigroup` you'll see a whole list of types that the `semigroups` package needs just to compile. Semigroups itself has `define`s to try to ameliorate this situation but the truth is that it's just too much work (at least given cabal in its current design) to enforce small dependency lists and coherence.

Long story short, it'd probably be best to just expose `Typeable` from the library, so I've sent a pull request. (As everyone knows, open source software collaboration is a variable experience. But even at my beginner level, it is possible to make small contributions.)

## The Equalizer

Remember last time I mentioned that we could destructure existential types? Now we can actually use this.

``````equalRC1 :: RequestConditionBox -> RequestConditionBox -> Bool
equalRC1 (RC a) (RC b) = testEqual a b``````

That looks pretty promising. But we haven't handled the case where `a` or `b` are themselves a `RequestConditionBox`

``````equalRC2 :: RequestConditionBox -> RequestConditionBox -> Bool
equalRC2 a1@(RC a) b1@(RC b) = eq3 (cast a) (cast b)
where eq3 (Just x) _ = equalRC2 x b1
eq3 _ (Just y) = equalRC2 a1 y
eq3 _ _ = testEqual a b``````

Well, that's kind of fun, but an alternative formulation is arguably better:

``````infixl 3 <|!> -- Left associative, use same precedence as <|>
(<|!>) :: Maybe a -> a -> a
(<|!>) = flip fromMaybe``````
``````equalRC4 :: (Typeable a, Eq a) => a -> RequestConditionBox -> Bool
equalRC4 x (RC y) = a <|> b <|!> c
where a = equalRC3 x <\$> (cast y)
b = equalRC3 y <\$> (cast x)
c = testEqual x y``````

`<|>` is a fairly general function, but in general it means "take the first valid parameter". Its type is

``(<|>) :: Alternative f => f a -> f a -> f a``

Here, just remember that `Maybe` is an `Alternative`. I've also introduced my own infix operator `<|!>` to get me out of `Maybe` land. (Hey, I don't even need an extension for this!)

We now have a vastly better implementation of `Eq`:

``````instance Eq RequestConditionBox where
(==) == equalRC4``````

(Aside: there's a very interesting looking function in `Data.Typeable` called `gcast` that I thought could be useful here, but I couldn't figure it out, so everything here stays at the `cast` level.)

## Designed By An Idiot In London

Let's load what we're got into a REPL.

``````> :m + Main
> :m + Data.List
> :m + Network.HTTP.Types
> let td = [RC methodGet, RC methodGet, RC (RC methodGet), RC http10, RC http11]
> nub td``````

gives us

``[RC "GET",RC HTTP/1.0,RC HTTP/1.1]``

Well, that's demonstrated that `Eq` works. But it also demonstrates something else: Eq isn't actually what we wanted in the first place. Really we want to be unifying to `[RC "GET",RC HTTP/1.1]`. To do that, we're going to have to rip up everything we've done so far and start again.

FOOTNOTE: Elise Huard pointed me to the AdvancedOverlap page on the wiki, which details techniques for branching your code by typeclass rather than type. In practice, I decided to just make everything an instance of `Eq`, which isn't so much of a problem given the problem domain I'm working within.

# A Route To Learning The Haskell Type System

TL;DR I start trying to write a library and get sidetracked into learning about Haskell's type system.

So last time, I talked about Wai and how you could use it directly. However, if you're going to do that, you'll need a routing library. So, let's talk about how we could build one up. One of the first things you'd need to do is to provide simple boolean conditions on the request object.

It turns out that this raises enough questions for someone at my level to fill more than one blog post.

``````{-# LANGUAGE TypeSynonymInstances #-}
{-# LANGUAGE FlexibleInstances #-}
``````import qualified Network.Wai as Wai
import qualified Network.HTTP.Types as H``````

So, how should we define conditions? Well, the Clojure model of keyword and string isn't going to work here, because the `Wai.Request` object is heavily strongly typed. So how about instead we just use the expected values and deduce the key from the type?

So, we're going to want to implement the same method for several different types. There's several different ways of doing that: * Create a union/enum class. This is a good approach, but not extensible. * Create a typeclass, which is extensible. * Create a type family, which is also extensible, but I don't really understand.

With that in mind, let's create our first typeclass!

``````class RequestCondition rc where
isMatch :: Wai.Request -> rc -> Bool``````

So, in English this says "If the type `rc` is a `RequestCondition` then there is a method `isMatch` which takes a `Wai.Request` and an `rc` and returns a `Bool`." This is pretty interesting from an OO standpoint. The OO representation would look like `rc.isMatch(request)`. A Clojure protocol would change this to `(isMatch rc request)`. In practice, it doesn't matter: what's happening is that there's dynamic dispatch going on on the first parameter.

In the Haskell case, there's no dynamic dispatch in sight and the first parameter isn't special. `isMatch` on `HTTPVersion` and `isMatch` on `Method` are different functions.

We can now implement the `RequestCondition` for some obvious data types.

``````instance RequestCondition H.HttpVersion where
isMatch = (>=) . W.httpVersion``````

So, here we've said "calling `isMatch` with a `HttpVersion` as a parameter calls `(>=) . W.httpVersion` i.e. checks the request is using the version specified. We'd probably need a more sophisticated way of dealing with this if we were writing a real system.

``````instance RequestCondition H.Method where
isMatch = (==) . W.requestMethod``````

This is much the same, with one wrinkle: `H.Method` isn't actually a type. It's a type synonym. In C++ you'd introduce one with `typedef`, in C# with `using`. Haskell, because it likes to confuse you, introduces something that is not a type with the keyword `type`. If you look up method on Hackage you see:

``type Method = ByteString``

You might wonder why this matters. The answer is that the Haskell standard doesn't allow you to declare instances of synonyms. You can understand why when you realize that you might have multiple synonyms for `ByteString` and shoot yourself in the foot. However, for now I'm going to assume we know what we're doing and just switch on `TypeSynonyms` in the header.

Let's do one more, because three's a charm.

``````instance RequestCondition H.Header where
isMatch = flip elem . W.requestHeaders``````

We'd need (a lot) more functionality regarding headers, but let's not worry about that now. However, again this will fail to compile. This time H.Header is a type synonym, but a type synonym for a very specific tuple.

``type Header = (CIByteString, ByteString)``

Problem is, Haskell doesn't like you declaring instances of specific tuples either. This time, you need `FlexibleInstances` to make the compiler error go away. To the best of my knowledge, `FlexibleInstances` is much less of a hefalump trap than `TypeSynonyms` could be.

For fun, let's throw in a newtype

``newtype IsSecure = IsSecure Bool``
``````isSecure :: IsSecure
isSecure = IsSecure True``````
``````instance RequestCondition IsSecure where
isMatch r (IsSecure isSecure) = W.isSecure r == isSecure``````

## Under Construction

How about when we've got multiple conditions to apply? Well, if we were writing Java, we'd be calling for a composite pattern right now. Let's declare some types for these.

``````newtype And rc = MkAnd [rc]
newtype Or rc = MkOr [rc]``````

I described `newtype`s back in Fox Goose Corn Haskell. Note that there's no reference to `RequestCondition` in the declaration. By default, type variables in declarations are completely unbound.

Before we go any futher, let's fire up a REPL (if you're in a Haskell project right now you can type `cabal repl`) and take a look at what that does:

``````data And rc = MkAnd [rc]
:t MkAnd
MkAnd :: [rc] -> And rc``````

Yes, `MkAnd` is just a function. (Not exactly, it can also be used in destructuring, but there isn't a type for that.) Let's try expressing it a different way while we're here:

``````:set -XGADTs
data And2 rc where MkAnd2 :: [rc] -> And2 rc``````

(You'll need to hit return twice) Now we're saying "`And2` has one constructor, `MkAnd2`, which takes a list of `m`. The GADTs extension does way more than this, some of which I'll cover later on, but even then I'm only really scratching the surface of what this does. For now I'll just observe how the GADTs extension provides a syntax that is actually more regular than the standard syntax.

Incidentally, I could have called `MkAnd` just `And`, but I've avoided doing so for clarity.

## Composing Ourselves

With the data types, we can easily write quick functions that implement the `RequestCondition` typeclass.

``````instance (RequestCondition rc) => RequestCondition (And rc) where
isMatch r (MkAnd l) = all (isMatch r) l``````
``````instance (RequestCondition rc) => RequestCondition (Or rc) where
isMatch r (MkOr l) = any (isMatch r) l``````

The most interesting thing here is that we haven't said that `And` is an instance of `RequestCondition`, we're say that it is if its type parameter is an instance of `RequestCondition`. Since data types normally don't have type restrictions themselves, this is the standard mode of operation in Haskell.

So, now I can write

``Or [H.methodGet, H.methodPost]``

and it'll behave. So we're finished. Right? Not even close.

What if we wanted to write

``And [H.methodGet, H.http10]``

It's going to throw a type error at you because HTTP methods aren't HTTP versions. If you take a look at the declaration, it says "list of `rc`s that are instances of `RequestCondition`" not "list of arbitrary types that are instances of `RequestCondition`". If you're used to OO, (and I have some bad news for you if you're a Clojure programmer, that means you) this makes no sense at all. If you're a C++ programmer, this is going to make a lot more sense. You see, when you do that in Java you're telling Java to call through a vtable to the correct method. Haskell doesn't have pervasive vtables in the same way. If you want one, you're going to have to ask nicely.

## Pretty Please and Other Existential Questions

What we want, then, is a function that boxes up a `RequestCondition` and returns a type that isn't parameterized by the original type of the `RequestCondition`. What would that function look like?

``boxItUp :: (RequestCondition rc) => rc -> RequestConditionBox``

Hang on, that looks like the type of a constructor! Except for one really annoying little detail: as I said before, you can't put type restrictions in `data` declarations.

Except you can, if you enable GADTs.

``````data RequestConditionBox where
RC :: (RequestCondition rc) => rc -> RequestConditionBox``````

`RequestConditionBox` is what's known as an "existential type". As I understand it that should be interpreted as "`RequestConditionBox` declares that it boxes a `RequestCondition`, but declares nothing else". So its quite like declaring a variable to be an interface.

Since I wrote this, I've learned that existential types are indeed very like interfaces in C#/Java: they are bags of vtables for the relevant type classes. They don't expose their parameterization externally, but destructuring them still gets the original type out. This is bonkers.

It just remains to actually implement the typeclass:

``````instance RequestCondition RequestConditionBox where
isMatch r (RC m) = isMatch r m``````

And now we can finally write

``And [RC H.methodPost, RC isSecure]``

And the compiler will finally accept it. Not quite as pretty as in an OO language where polymorphism is baked into everything, but keeping the character count low isn't everything. We've traded implicit polymorphism for explicit polymorphism.

So we're done, right? Well, we could be, but I want to go further.

## The Power of Equality

If you take a look, what we've built looks very much like a toy interpreter (because it is one). What if we wanted a toy compiler instead? In particular, imagine that we really were building a routing library and we had thousands of routes. We might want to only check any given condition once by grouping, for example, all of the `GET` routes togther.

Now, you could leave that to the user of the library, but let's pose the question: given two `RequestCondition`s, both of which may be composite, how do you determine what conditions are common between the two?

One route is to backtrack, and look at HLists. I think that's probably an extremely strong approach, but I really haven't got my head around the type equality proofs-as-types stuff. Another approach is add some stuff to `RequestCondition` to track the types in some way. It turns out there's a way to get the compiler to do most of the work here, so I'll talk about that next time.

FOOTNOTE: On the Reddit discussion it was pointed out that `RequestConditionBox` is an example of the existential type anti-pattern. To summarize: if all you've got is a bunch of methods, why not just have a record with those methods as properties? If all you've got is one method, why not just use a function.

This is a completely valid criticism of the code in this post as a practical approach. However, we wouldn't have learned about existential types in the first place, and we couldn't make functions implement `Eq` and `Show`. Implementing `Eq` is the subject of the next post.

The commenter also added an elegant implementation of the functionality given above in terms of pure functions.

EDIT: Lennart Augustsson clarified that existential types do indeed construct vtables. So "boxing" something in an existential type is very like casting a struct to an interface it implements in C#. I should also clarify that the word bonkers used in the above text was meant as a good thing. :)

# Hello World Web Application in Haskell

So, I'm learning Haskell. I've done the Yorgey course and want to write a web app. How do I start? Should I learn Snap or Yesod? Well, the short answer is no.

Here I'm going to outline the creation of the simplest possible Haskell "Hello World" web application.

## Wai Wai Pom Pom Pom

Snap and Yesod are both "big" web frameworks. Of the two, Snap aims to be the smaller. Both have their own web server, templating system and so on. Both are sufficiently complex to need a program to set up a starter project. Both have fairly sophisticated monad stacks to understand. They're also both phenomenal high-performance pieces of engineering.

What this means for a beginner is that you're going to spend as much time trying to get to grips with the framework as you are learning how to use Haskell. If like me, you're coming from Clojure, they both feel a bit more like Rails than Compojure.

So, are there simpler to understand models out there? Well, the equivalent of Compojure/Sinatra is Scotty. But I found the next level down again more interesting: Wai.

Wai corresponds most closely to Ring or Rack. It was intended to be a common API that Haskell web servers could expose. In practice, it's only Warp that really supports it. However, Warp is a damn fine web server so that shouldn't hold us back too much. Nearly every Ring app runs Jetty and hardly anyone really worries that the "standard" isn't as portable in practice as it is in theory.

## Setting up Hello World

To start, create a new directory. For our purposes we'll call it "example". Then we set up a completely blank project.

``````mkdir example
cd example
cabal sandbox init
wget http://www.stackage.org/lts/1.8/cabal.config
cabal init``````

The "sandbox" and "wget" lines I'll gloss over, but they basically constitute the best way I know to avoid what's known as "cabal hell". And believe me, you don't want cabal hell.

When you run the init command, you'll be asked a whole bunch of questions. The defaults are fine, just make sure you specify you're creating an executable. It'll create a file "example.cabal". You then need to go in and make it look like this:

``````-- Initial semele.cabal generated by cabal init.  For further

name:                example
version:             0.1.0.0
-- synopsis:
-- description:
author:              Rainbow Dash
maintainer:          rainbow.dash@gmail.com
category:            Web
build-type:          Simple
-- extra-source-files:
cabal-version:       >=1.10

executable semele
hs-source-dirs:      src
main-is:             Main.hs
-- other-modules:
-- other-extensions:
build-depends:       base >=4.7 && <4.8,
wai,
warp,
http-types

There's two import edits here. The first is that we specify `hs-source-dirs`. The default is that the Haskell files are dumped in the project's root directory, which is a lousy default. The other is that we set up our dependencies: wai, warp and http-types. Wai and http-types from our API, Warp our implementation. Note that dependencies are case-sensitive.

You may also be wondering why I haven't specified any version constraints. That's because we've set them up in the `cabal.config` instead. Welcome to the new world of LTS Haskell.

## Writing Hello World

``````mkdir src
cd src``````

Now create `Main.hs`.

``{-# LANGUAGE OverloadedStrings #-}``

We need this because Wai uses `ByteString`s rather than `String`s, and overloaded strings makes using them lower friction.

``````import qualified Network.Wai as W
import qualified Network.HTTP.Types.Status as HS
import qualified Network.Wai.Handler.Warp as Warp``````

I'm qualifying everything for clarity. In practice, I do this a fair bit even when I'm not writing a blog post.

``````main :: IO ()
main = main = do
putStrLn "Starting Web Server..."
Warp.runSettings Warp.defaultSettings app``````

So, all we're saying here is "Run the `app` with the default settings for a Warp server." The default port is 3000.

Finally, we need the `app` itself:

``app :: W.Application``

Let's take a huge detour and examine what that actually means.

## Understanding W.Application

Now, the type of `app` is `W.Application`, but that tells us nothing. So let's look it up (LTS has a hoogle, search for `Wai.Application`). You'll find

``type Application = Request -> (Response -> IO ResponseReceived) -> IO ResponseReceived``

So, it's a alias for a type of function. However, the type's way more complex that we were expecting. What were we expecting? Well, in Ring the type's more like

``type ApplicationRing = Request -> Response``

Take a request, return a response. However, in order to allow for correct resource management, it uses a continuation passing style instead. (I'm hoping to expand on that in another post.) So instead, you need a callback. As you see, we called that `respond`.

What's `respond`'s type? Well, it's got to take a response. At this point I hit the limits of my understanding. I'd have made the function return `()`, but instead it returns `ResponseReceived` which appears to be a placeholder type. Finally, obviously `respond` is going to have to write to a socket, so it's going to have to incorporate the `IO` monad. Now, in most of the more complex APIs, what you find here is a monad transformer stack with IO somewhere in the mix. In Wai, you just get a naked `IO ResponseReceived` and can build your own later.

To summarize, the type of `respond` is `Response -> IO ResponseReceived` and that means "when you call it with a response it will do some IO and return that it's been processed`.

Finally, `Application` expects `IO ResponseReceived` to be returned from the function. I believe this to be practically motivated: nearly every handler is going to want to call respond as the last thing it does, and this means that the types work when you do that.

## You Had Me At Hello

So, now we've understood the type, let's write the function

``app request respond = respond \$ W.responseLBS HS.status200 [] "Hello World"``

To unpack this: when you receive a request, `respond` using status 200 (success), no headers (`[]`) and byte string "Hello World".

So, that's about the simplest thing we can possibly do without writing our own web server.

## Let's Be Frank

So, how does this compare to Sinatra's famously good home page? Well, for a start we have three files instead of one. However, two of those files are devoted to ensuring that our dependencies don't mess us around, if you want to do the same in Ruby, you'll be setting up bundler, using a gemfile.lock in addition to your normal gemfile, so three files again.

Haskell actually comes out slightly ahead here if you're willing to forgo some flexibility, in that the `cabal.config` is repeatable and upgrading is a matter of trying a new `cabal.config`/ reverting if it doesn't work.

In comparison, bundler generates a lock file dependent on your current gemfile. If you need to add another library later, it's up to you to figure out which versions are compatible with your code.

On the other hand, if you need more flexibility, you're going to encounter cabal hell pretty quickly. Good luck.

We've got three dependencies instead of one. That's a pity. But it comes from the two sources:

• We've got to import types declaring interfaces as well as just implementation code.
• We don't have the web server appearing by magic.

On the other hand, Sinatra's actually provided a routing library, and we don't have one yet. But we could have used Scotty instead.

## Keep On Running

So, let's see it in action. Get back to the root project directory and type

``cabal install && dist/*/build/example/example``

and navigate to http://localhost:3000/. Hey presto, you've served a web page. Looking at the headers, all that it's specified is a Date, the Server and Transfer-Encoding, so we'll definitely have a bit more work to do to for a full experience.

FOOTNOTE: Quite a few people have remarked that the comparison section isn't really fair on Haskell in that I've implemented something at the Rack/Wai level, rather than the Sinatra/Scotty level, which is true. However, I wanted to use Wai rather than Scotty to avoid going into monads and monad transformers and ultimately, I think the Haskell one is still quite concise and beautiful in a very precise manner.

EDIT:A number of people have pointed out that modern ruby is indeed capable of precise version locking. I've updated and expanded the comparison to reflect that.

EDIT:Originally I believed that Wai's continuation passing style was due to asynchronous concerns. Instead, it's driven by resource management concerns. I've corrected the line.

# Fox Goose Corn in Haskell for Clojure Programmers

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.Set` is 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 d` means 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 `Generation`s would be better if we used lenses, but lets stick to things in the base libraries.

We need to map the function that generates new states to a function that creates new `Generation`s. 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 `a` implements `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 a` is 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.

# Design Patterns: Happy Birthday and Goodbye

One of the biggest lies we tell starting developers is that design patterns are language independent. Whilst true at a high level, the truth is that a programmer in a modern programming language can junk most of the Gang of Four book. A couple of days ago, it was twenty years old. It's time to celebrate its lasting positive influences, and then bury it.

Some things are potentially useful as terminology for discussing with people, but others aren't even useful as that. The really obvious example is the template pattern: if you're programming in a language that can use functions as values it's utterly meaningless. Another is iterator: most programming languages have a list/sequence implementation and you just use that.

Prototype, equally is meaningless for two, entirely opposite, reasons: first, the whole concept originates in C++ where you can perform a raw memory copy. In a language such as Java that doesn't have one it's so cumbersome you'll prefer a factory method. In a language such as F# or Clojure, ubiquitous persistence data structures mean that everything's a prototype.

Command is basically a pattern that replaces functions with objects. In a functional programming language, this is just the normal way you do things. In languages such as Python and Clojure where objects can act as functions the line is further blurred. But that's nothing compared to what you can do with Clojure's multimethods.

## Multimethods and Protocols

Quite a few patterns are just workarounds for the painfully restricted dispatch patterns in old OO languages. The visitor and adapter patterns are both ways of circumventing the closed nature of classes in C++/Java. When you can just associate new methods with existing data structures, even third party code, you just don't need them.

Also, if you understand multimethods for more than just class based dispatch, you see that it subsumes the state pattern.

``````(defmulti state-pattern (fn [tool data] tool))
(defmethod state-pattern pen-tool
[tool data]
nil)``````

``````(defmulti strategy-pattern (fn determine-strategy [tool data] ...))
(defmethod state-pattern :strategy1
[tool data]
nil)``````

In practice, you can use multimethods to mix and match dispatch on raw parameter value (state), dispatch on computed value (strategy) and dispatch on class (visitor). Similar effects can be achieved using Haskell's type features.

## Trivial

Then there's stuff that's just a special case of something more general. Chain of responsibilty in Clojure is easily implemented using the `some` function:

``````(defn chain-of-responsibility
([elements] (partial chain-of-responsibility elements))
([elements data] (some #(% data) elements)))``````

Is chain of responsibility really useful terminology here, or is it just "using the `some` function"?

Then there's ones that are just plain outdated: observer and mediator are rarely a better choice than a decent pub/sub mechanism. Heck, even your language's event system is often a better choice. And I think everyone's got the message about singleton by now.

## Outdated

I'm concerned this will be seen as down on the whole concept of patterns. Actually, high level patterns, the kind that Martin Fowler talks about are fine and last a long time. But our understanding of patterns constantly evolves (see pub/sub) and the ergonomics of specific patterns varies wildly between languages. GoF was a great book, and made a huge positive impact, but it's time to take it off our shelves.

# Let's Write a Transducer!

For me, Rich Hickey's original post on transducers raised more questions than it answered. Stian Eikeland wrote a good guide on how to use them, but it didn't really answer the questions I had. However, there's an early release of Clojure 1.7, so I thought I'd take a look.

``````(def z [1 2 3 4 5 6])
(sequence (filter odd?) z)
;;; (1 3 5)``````

Okay, so far so good, we understand how to use an existing transducer to create a sequence.

Now, is identity a transducer?

``````(sequence identity z)
;;; (1 2 3 4 5 6) ``````

Perfect. Now let's try doing it ourselves. We'll write a transducer that preserves all its input.

## Arity Island

Rich says the type of a transducer is (x->b->x)->(x->a->x). In practice, arity matters in Clojure, so it's really (x->b-x)->(x,a)->x. So let's write `my-identity`

``````(defn my-identity [yield] (fn [x b] (yield x b)))
(sequence my-identity z)
;;; ArityException Wrong number of args (1) passed to:
;;; user/my-identity/fn--1347  clojure.lang.AFn.throwArity (AFn.java:429)``````

Wait, it's only expecting one argument? Let's try one

``````(defn my-identity [yield] (fn [x] (yield x)))
(sequence my-identity z)
;;; ArityException Wrong number of args (2) passed to:
;;; user/my-identity/fn--1342  clojure.lang.AFn.throwArity (AFn.java:429)``````

Unsurprising. Let's combine the two.

``````(defn my-identity [yield] (fn ([x b] (yield x b)) ([x] (yield x))))
(sequence my-identity z)
;;; (1 2 3 4 5 6) ``````

OK. So, a transducer is actually two functions. What the heck are these functions being passed?

``````(defn my-identity [yield]
(fn ([x b] (println "Arity2:  " x) (yield x b))
([x] (println "Arity1:  " x) (yield x))))
(sequence my-identity z)
;;; StackOverflowError   clojure.lang.RT.boundedLength (RT.java:1697)``````

Oh dear. Maybe we can see the class instead:

``````(defn my-identity [yield]
(fn ([x b] (println "2A " (class x)) (yield x b))
([x] (println "1A " (class x)) (yield x))))
(sequence my-identity [5 7 9])
(2A  clojure.lang.LazyTransformer
2A  clojure.lang.LazyTransformer
5 2A  clojure.lang.LazyTransformer
7 1A  clojure.lang.LazyTransformer
9)``````

Well, that's a bit of a mess, but we can see the 5, 7 and 9 streaming out. Weirdly, they seem to be coming out slightly too late. And the arity-1 function is called at the end. It's not clear what you can usefully do with it's parameter other than pass it through since it's not fixed, has no guaranteed protocols and in the case of LazyTransformer, blows up if you try to evaluate it.

If you take a look at actual transducers, you'll see there's a third, zero-arity function declared as well. I haven't discovered what that's for yet.

## State of Play

So what's that arity-1 function for, then? Well, the doc string for drop gives us a clanger of a clue:

``Returns a stateful transducer when no collection is provided.``

Transducers can have state. They start when the yield function is passed them, and finish when the arity-1 function is called, and you can clean up resources when it ends. This start/reduce/finish lifecycle is actually vital to making `drop` and other reducers work.

OK, this is starting to look an awful lot like the IObserver interface in C#. (The Subcribe method corresponds to the initial start step.) That suggests the arity zero function is for some form of error handling, but I haven't managed to trigger it.

Okay, now let's try something a bit harder. Let's repeat our input.

``````(defn duplicate [yield]
(fn ([x b] (yield x b) (yield x b)) ([x] (yield x))))
(sequence duplicate [1 2 3 4 5 6])
;;; (1)``````

What the heck happened there? We ignored the result of the first call to `yield`. Let's fix that.

``````(defn duplicate [yield]
(fn ([x b] (yield (yield x b) b)) ([x] (yield x))))
(sequence duplicate [1 2 3 4 5 6])
(1 1 2 2 3 3 4 4 5 5 6 6)``````

Perfect! It's a mystery to me how exactly it failed, but we've gained a bit more insight: you can only do calls to `yield` by passing the result of one into the first parameter of the next.

So, here's what we've learned:

• A transducer is a function that takes one parameter and returns a "function"
• It has a start/reduce/finish lifecycle. The finish step can't transform the result further.
• It can have state.
• Calls to `yield` in the reduce step have to be well-behaved.

I'd like to write some more, but this is easily enough for this post.

Functors are all very well, but they only allow you to map with a function that takes only one parameter. But there's plenty of functions that take more than one parameter, including useful ones like add and multiply. So how do we want to multiply to work on nullable integers?

• 2 times 3 should be 6
• 2 times null should be null
• null times 3 should be null
• null times null should be null

There's something else we need to do. What if 2 is just an integer, not a nullable integer? Really, we need to be able to promote an integer to a nullable integer. The more parameters a function has, the more likely one of them isn't in exactly the right format. Haskell calls this function `pure`. (+)

Now let's get a bit more complicated. What about multiplying two lists together? Multiplying `[2]` and `[3]` should obviously give `[6]`. But what happens if you're multiplying `[2,3]` and `[5,7]`? Turns out there's at least three sensible answers:

• Multiply the pairs in sequence: `[10,21]`
• Multiply the pairs like a cross join: `[10,14,15,21]`
• Actually, you could also iterate the first sequence first `[10,15,14,21`

## More than one way to skin a list

Let's just concentrate on the first two. How are they going to deal with lists of different length?

• `[2] * [1,3]` should be `[2]` OR
• `[2] * [1,3]` should be `[2,6]`

But what if the first parameter isn't a list. What should that look like? Well, `2 * [1,3]` should definitely be `[2,6]`. But that means that, depending on how we generalise multiplication, we also need to generalise turning a number into a list.

• To multiply like a cross join, `2` can just become `[2]`
• To multiply the pairs in sequence `2` needs to be `[2,2,2,2,2,...]`, an infinite sequence of `2`s.

So, generalizing multiple-arity functions to functor contexts isn't as obvious as it is for single-arity functions. What on earth do we do about this? Well, the approach Haskell goes with is "pick an answer and stick with it". In particular, for most purposes, it picks the cross join. But if you want the other behaviour, you just wrap the list in a type called `ZipList` and then ZipLists do the pairwise behaviour.

## Back to the Functor

So, how should we handle the various examples of functors that we covered in the first part? We've already dealt with nullables and lists and sets are a dead loss because of language limitations.

Multiplying two 1d6 distributions just gives you the distribution given by rolling two dice and multiplying the result. Promoting a value e.g. 3 to a random number is just a distribution that has a 100% chance of being 3.

You can multiply two functions returning integer values by creating a function that plugs its input into both functions and then returns the product of the results. You can promote the value 3 to a function that ignores its input and returns 3.

How about records in general? Well, here's the thing: you can't promote a record without having a default value for every field. And that isn't possible in general. So, while you can undoubtedly make some specific datastructures into applicatives, you can't even turn the abstract pair `(a,b)` (where you're mapping over `a`) into an applicative without knowing something about `b`.

We could make the mapping work for pair if we were actually supplied with a value. But that doesn't make sense, does it? How about, instead of `(a,b)` we work on functions `b -> (a,b)`. Now we can map `a`, on single and multiple-arity functions, and just leave the `b` input and output values well alone. It turns out this concept is rather useful: it's usually called the State Monad.

## Would you like Curry with your Applicative?

Up until now, I've mostly talked about pairwise functions on integers. It's pretty obvious how you'd generalize the argument to arbitrary tuples of arbitrary input times. However, it turns out that the formulation I've used isn't really that useful for actual coding, partly because constructing the tuples is a real mess. So let's look at it a different way.

Let's go back to multiplying integers. You can use the normal `fmap` mapping on the first parameter to get partially applied functions. So our `[2,3] * [5,7]` example gives up `[2*,3*]` and `[5,7]`. Now we just need a way of "applying" the functions in the list. We'll call that `<*>`. It needs to do the same thing as before and the promotion function, `pure` is unchanged.

It turns out that once you've got that, further applications just need you to do `<*>` again, so if you've got a function `f` and you'd normally write `f a b c` to call it, you can instead write

``f <\$> a <*> pure b <*> c``

Assuming `a` and `c` are already in the correct type and b isn't. This is equivalent to

``pure f <*> a <*> pure b <*> c``

but in practice people tend to write the dollar-star-star form. Finally, you can also write

``(liftA3 f) a (pure b) c``

which is much more useful when you're going pointfree.

## And finally...

So, here's the quick version:

• a functor that can "lift" functions with multiple parameters is termed an "applicative functor", "idiom" or just "applicative"
• a functor is uniquely defined by the data type you're mapping to(*)
• some data structures like list, however, give rise to multiple possible implementations of `Applicative`

Functors have been well understood for a long time, and monads provided the big conceptual breakthrough that made Haskell a "useful" language. The appreciative of applicative functors as an abstraction that occupies a power level between the two is a more recent development. When going around the Haskell libraries you'll often discover two versions of a function, one of which is designed for applicatives and one for monads but they're the same function. It's just that the monad version was implemented first. With time, the monad versions will be phased out, but it's going to take a long tuime. You can read more about the progress of this on the Haskell wiki.

If you want a much more rigorous approach to what I've been talking about here, read Brent Yorgey's excellent lecture notes.

(+) and `return`, for historical reasons.

(`*`) Indeed, and this is awesome, Haskell will just automatically generate
the Functor `fmap` function for you.