Thursday, December 27, 2012

Following Types

Writing Haskell can be hard. Especially with typeclasses like Monad, Moniod and Applicative, it's sometimes hard to figure out what exactly what some function is going to do. Eventually you can be a Haskell god and feel it in your bones or something but until that time, I suggest some simple advice, follow the types.

Haskell's type system is pretty far off from anything else I've used. It provides a degree of certainty when using it. It can't guarantee the correctness in all cases (cough cough halting problem) but it can certainly help you reason about a complex piece of applicative or monadical code.

Let's take a look at a few quick examples,

Simple Example

Let's take a look at a quick and simple example. You can probably figure this one out if you've programmed much in Haskell but it illustrates the point quite nicely:

map (+1) [1..9] => [2, 3, 4, 5, 6, 7, 8, 9, 10]

Here and throughout the article I use the => to denote evaluation, read it as "evaluates to"

Let's take a look at the type signature here for those who don't know what partial applications are. (GHCi's :t is a good for this)
map    :: (a->b) -> [a] -> [b]
(+)    :: (Num a) => a -> a -> a 
--(you can ignore the (Num a) => part for now)
[1..9] :: [a]

Reading through these. map takes in a unary function and a list of inputs to that function, it then returns a list of outputs from the function. We want to add one to each element in the list, so how do we turn (+) into a "increment by one" function? First let's look at the type of plus. It takes in some sort of number, another of the same sort of number, and adds them together. Thanks to the magic of currying all we have to say is (+1).

This gives + a number, in this case 1, and then since the type is
a->a->a, when we give it 1, it returns a function with the type a->a. And there is our unary function! Then it's pretty easy to get, since [1..9] is a list of numbers, map is perfectly happy to take that with (+1) and our piece of code works beautifully.

Moderate Example

Let's take a look at more complicate ahem fun example. Because Monads are so common in Haskell and people seem to be scared by them, let's do something with them.

For this example we're going to implement mapM (not to be confused with mapM_ from Data.Foldable).

The type of mapM is:

mapM :: (Monad m) => (a -> m b) -> [a] -> m [b]

We're supposed to take a list of some values, some function that takes one of the values and transforms it to a type wrapped in a monad, and return 1 monad wrapping a list of those types. Ok...

Let's quickly review what tools we have available:

(>>=)  :: (Monad m) => m a -> (a -> m b) -> m b
(>>)   :: (Monad m) => m a -> m b -> m b
return :: (Monad m) => a -> m a

The one that strikes me as being useful is (>>=) or bind. With bind we can extract the value from a monad "wrapper", change it in some way, then put it back into the monad's box.

Let's try defining mapM recursively, just as map is defined. Then our base case is pretty easy:

mapM f [] = return []

Now comes the tricky part, how do we take one value of type a, and fuse it into a list of type m [b]... We know how to turn a into an m b. Using that and bind, we get this:

mapM f (a : as) = next >>= (\b -> rest >>= (\bs -> return $ b:bs))
    next = f a
    rest = mapM f as

-- Equivalently using do-notation

mapM f (a : as) = do
  b  <- f a
  bs <- mapM f as
  return $ b : bs

So let's justify to ourselves that this makes sense. Let's look at the non-do version since it's easier to see the types.

First we take next, which as the type m b, unwrap it and forget about it for a moment, then unwrap rest which as type m [b], append the two of them together and use return on the whole thing. This gives us an end type of m [b], exactly what we wanted!

On a related side note, that pattern of unwrapping 2 things and doing something with them is so common there's a function for it, liftM2. This has the type:

liftM2 (Monad m) => (a -> b -> c) -> m a -> m b -> m c

Well hey, we have (:), next and rest, which have the types

(:)  :: a -> [a] -> [a]
next :: m b
rest :: m [b]

Based on that, all we really need is

mapM f (a:as) = liftM2 (:) next rest
    next = f a
    rest = mapM f as
    -- NOT rest = f as Thank you Anton

This is similar to an applicative style in Haskell and tends to be more concise than it's monadic cousin. Let's explore it further in the next example.

An Exercise in the Applicative

For our last exercise let's take an example of working but verbose code and make it more terse and idiomatic.

Here's the code we want to fix:

combine :: (b -> c -> d) -> (a -> b) -> (a -> c) -> a -> d
combine f f1 f2 a = f (f1 a) (f2 a)

It could be argued that in this case this code is just fine, but for the sake of argument let's turn it into something more applicative. We're going to use 2 functions in particular

<*> :: (Applicative f) => f (a -> b) -> f a -> f b
<$> :: (Functor f) => (a -> b) -> f a -> f b

Since every Applicative instance is also a functor instance, we can safely use <$> on applicatives. As an exercise to the reader, verify that this new version is the same as the previous using the type signatures above:

combine f f1 f2 = f <$> f1 <*> f2

Good luck!


  1. I guess proper definition for mapM is
    mapM f (a:as) = liftM2 (:) next rest
    next = f a
    rest = mapM f as
    instead of
    mapM f (a:as) = liftM2 (:) next rest
    next = f a
    rest = f as