Haskell monads

Some weeks ago, I spent a couple of days working through some Haskell with a colleague of mine. This is some of the stuff we went through.

1. Haskell exercises for beginners to get back in the swing of things.


2. Write implementations for:

   mflatten :: Maybe (Maybe a) -> Maybe a
   mmap     :: (a -> b) -> Maybe a -> Maybe b
   
   lFlatMap :: [] a -> (a -> [] b) -> [] b
   mFlatMap :: Maybe a -> (a -> Maybe b) -> Maybe b



3. Observe lFlatMap and mFlatMap can be written with the same pattern. How can we reduce the "duplication"?


4. Derive flatten from flatMap:

   class FlatMap f where
     flatMap :: f a -> (a -> f b) -> f b
   
   flatten' :: (FlatMap f) => f (f a) -> f a
   flatten' = error "todo"



5. Given pure:

   class Pure p where
     pure :: a -> p a

   and flatMap, derive map:

   map' :: (FlatMap f, Pure f) => f a -> (a -> b) -> f b
   map' t f = error "todo"



6. Let's give the combination of flatMap and pure a name, perhaps Monad:
   

   class Monad' m where
     flatMap :: m a -> (a -> m b) -> m b
     pure    :: a -> m a

   A diagram to describe the relationships between our functions so far:
   
   


7. Write the following functions:
   

   liftM0    :: (Monad' m) => a -> m a
   liftM1    :: (Monad' m) => (a -> b) -> m a -> m b
   liftM2    :: (Monad' m) => (a -> b -> c) -> m a -> m b -> m c
   liftM3    :: (Monad' m) => (a -> b -> c -> d) -> m a -> m b -> m c -> m d
   ap        :: (Monad' m) => m (a -> b) -> m a -> m b
   sequence' :: (Monad' m) => [m a] -> m [a]
   mapM'     :: (Monad' m) => (a -> m b) -> [a] -> m [b]

   
   Observe:
   
   • liftM0 and liftM1 are just pure and map respectively
   
   
   • liftMn for n >= 2 can be written as:
     
     
     
     • n x flatMap + pure
     
     
     • (n - 1) x flatMap + map
     
     
     • liftM(n - 1) + flatMap
     
     
     • liftM(n - 1) + ap
   
   
   • sequence' and mapM' can each be written in terms of the other


8. Finally, note the Monad laws.

Step 2 Notes
I found it natural to write:

lFlatMap xs f = concat $ map f xs

mFlatMap Nothing _  = Nothing
mFlatMap (Just x) f = f x

However, given the similar type signatures, I can instead write:

mFlatMap xs f = mflatten $ mmap f xs

Step 3 Notes
After some reflection I realised it is important is to ignore the function names and implementations. I had internalised the concept of map as a minor generalisation of List.map i.e. traversing across elements in a 'container' and applying the same function to each one, which didn't quite fit with Maybe.

The key is simply the function signatures. If I have some functions f and g, such that

f :: (a -> b) -> t a -> t b
g :: t (t b) -> t b

then I can automatically construct a function h

h :: t a -> (a -> t b) -> t b

where h is simply the composition of g with f and nothing more can be said about it.

It does not matter that f is called map for List and it is not helpful to compare implementations of f for two different types t, looking for similarities beyond the type signature.

For me this is a case where attaching a meaning to a name impeded the process of abstraction.