Let's see if I get this by writing a little newbie tutorial for myself using literal Haskell syntax.
I will import Control.Arrow since fmap on a pairs transforms the second coordinate value,
and when transforming pairs, I sometimes need to transform the first coordinate value...
> import Control.Arrow
To understand the (fmap.fmap.fmap) thing, I will create a simple tutorial,
mainly for myself to get a better understanding.
Suppose we have a pair:
> p :: (Bool, [Char])
E.g.
> p = (True,"Reactive")
The "type graph" (pardon my lack of knowledge of correct terminology) of p is
(,)
/ \
Bool []
|
Char
Since fmap is about transforming a structure into another structure,
let's suppose that - given any "instance" with a type signature like p -
we want to create a new instance p' at runtime that transforms
the string (at the second coordinate) into its length.
That's easy; we can use fmap (or Arrow.second) to do that:
< instance Functor ((,) a) where
< fmap f (x,y) = fmap (x, f y)
> tp :: (Bool,[Char]) -> (Bool,Int)
> tp = fmap length
>
> p' = tp p
fmap on pairs basically transforms the rightmost branch of our graph.
(,) (,)
/ \ / \
Bool [] --> Bool Int
|
Char
fmap always transforms the rightmost branch in the graph, since the kind of Functor is * -> *.
For example lets define an fmap on triples:
> instance Functor ((,,) a b) where
> fmap f (x,y,z) = (x,y,f z)
< fmap :: (c->d) -> (a,b,c) -> (a,b,d)
(,,) (,,)
/ | \ --> / | \
a b c a b d
To continue the (fmap.fmap.fmap) story, suppose we now nest p in a Maybe:
> m :: Maybe (Bool, [Char])
> m = Just (True, "Reactive")
Maybe
|
(,)
/ \
Bool []
|
Char
Again we want to transform the string into its length.
To do that we can use the fmap Maybe instance:
< fmap f Nothing = Nothing
< fmap f (Just x) = Just (f x)
The function we need to fmap on m is just tp!
> tm :: Maybe (Bool,[Char]) -> Maybe (Bool,Int)
> tm = fmap tp
>
> m' = tm m
So again this fmap transforms the rightmost branch underneath the Maybe
(which is the one and only branch underneath the unary Maybe type)
If we expand tm we get
< tm = fmap (fmap length) = (fmap . fmap) length
So here we have the first magical (fmap . fmap):
- the first fmap transforms the branch underneath the Maybe with (fmap (fmap length)),
- the second fmap transforms the right branch underneath the pair (,) with (fmap length).
We can also do this for functions. Suppose we now have
> f :: Char -> Maybe (Bool, [Char])
> f c = Just (c=='a', "Reactive")
The type graph of f is
(->)
/ \
Char Maybe
|
(,)
/ \
Bool []
|
Char
But function application also has an fmap instance!
It is just the same as function composition:
< instance Functor ((<-) a) where
< fmap f g = f . g
< fmap :: (b->c) -> (a->b) -> (a->c)
(->) (->)
/ \ -> / \
a b a c
Again the rightmost branch is transformed...
So to transform the string into its length but now in the f graph, we do
> tf :: (Char -> Maybe (Bool, [Char])) -> (Char -> Maybe (Bool, Int))
> tf = fmap tm
>
> f' = tf f
Expanding this gives
> tf' = (fmap . fmap . fmap) length
> f'' = tf' f
So the expression ((fmap.fmap.fmap) g) performs deep transformation
on the 3 rightmost branches of any type graph (that has fmap instances)
To transform a leftmost branch, we can use Arrow.first, for example:
> tf'' :: (Char -> Maybe (Bool,[Char])) -> (Char -> Maybe (String,[Char]))
> tf'' = (fmap . fmap . first) show
> f''' = tf'' f
Demo:
> main = mapM_ putStrLn
> [ showT p $ fmap length
> , showT m $ (fmap.fmap) length
> , showF f $ (fmap.fmap.fmap) length
> , showF f $ (fmap.fmap.first) show ]
>
> showT x t = show x ++ " ==> " ++ (show $ t x)
> showF f t = "\'a' -> "++show (f 'a') ++ " ==> \'a' -> " ++ show ((t f) 'a')
|(True,"Reactive") ==> (True,8)
| Just (True,"Reactive") ==> Just (True,8)
| 'a' -> Just (True,"Reactive") ==> 'a' -> Just (True,8)
| 'a' -> Just (True,"Reactive") ==> 'a' -> Just ("True","Reactive")
I think I learned something cool here: being able to perform deep transformations without writing a lot of boiler plate code.
Thank you!