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
pure :: a -> p a
and 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
flatMap :: m a -> (a -> m b) -> m b
pure :: a -> m a
A diagram to describe the relationships between our functions so far:
- 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
- Finally, note the Monad laws.
Step 2 NotesI 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 NotesAfter 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
hh :: 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.
