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.

- Haskell exercises for beginners to get back in the swing of things.
- 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 - Observe
`lFlatMap`

and`mFlatMap`

can be written with the same pattern. How can we reduce the "duplication"? - 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" - Given
`pure`

:class Pure p where

and

pure :: a -> p a`flatMap`

, derive`map`

:map' :: (FlatMap f, Pure f) => f a -> (a -> b) -> f b

map' t f = error "todo" - Let's give the combination of
`flatMap`

and`pure`

a name, perhaps`Monad`

:class Monad' m where

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

flatMap :: m a -> (a -> m b) -> m b

pure :: a -> m a - 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`

- n x
`sequence'`

and`mapM'`

can each be written in terms of the other

- Finally, note the Monad laws.

Step 2 Notes

I found it natural to write:

lFlatMap xs f = concat $ map f xsHowever, given the similar type signatures, I can instead write:

mFlatMap Nothing _ = Nothing

mFlatMap (Just x) f = f x

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 thatf :: (a -> b) -> t a -> t bthen I can automatically construct a function

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

`h`

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

`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:

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

I agree.

Post a Comment