Wednesday, October 29, 2008

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.

2 comments:

Quiz said...

"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."

You are right that those things don't matter, but one needs more than type signatures: one needs laws.

You need for f (i.e. fmap or liftM1) to obey the functor laws: fmap id = id, and fmap f . fmap g = fmap (f . g).

Brad Clow said...

I agree.