compose.org

Composition of Functors/Applicatives/Monads*

Functor

A functor is a map between categories.

fmap :: (Functor f) => (a -> b) -> f a -> f b

laws:

fmap id = id
fmap (f . g) == (fmap f) . (fmap g)

Functor composition

What do we mean?

fmap1 :: (Functor f           ) => (a -> b) -> f a     -> f b
fmap2 :: (           Functor g) => (a -> b) ->    g a  ->    g b
fmap  :: (Functor f, Functor g) => (a -> b) -> f (g a) -> f (g b)

Think: is it possible to map nested List/List of Maybe/Maybe List?

Functor composition

Functor composition is easy!

fmap1 :: (Functor f           ) => (a -> b) -> f a     -> f b
fmap2 :: (           Functor g) => (a -> b) ->    g a  ->    g b
fmap  :: (Functor f, Functor g) => (a -> b) -> f (g a) -> f (g b)
fmap f fga = let fa2fb = fmap2 f -- :: f a -> f b
             in fmap1 fa2fb fga
-- in short,
fmap f = fmap1 (fmap2 f)

Or, pointfree-ly:

fmap = fmap2 . fmap1

Preservation of Functor laws

Let’s check!

  fmap id
= fmap1 (fmap2 id)
= fmap1 id
= id

  fmap (f . g)
= fmap1 (fmap2 (f . g))
= fmap1 ((fmap2 f) . (fmap2 g))
= fmap1 (fmap2 f) . fmap1 (fmap2 g)
= fmap f . fmap g

Applicative

An Applicative is a functor with two extra natural transformations:

pure  :: a -> f a
apply :: f (a -> b) -> f a -> f b

Composition of Applicative

Given an Applicative f and an Applicative g, we need to derive:

pure  :: a -> f (g a)
apply :: f (g (a -> b)) -> f (g a) -> f (g b)

Deriving Applicative composition: pure

pure is straightforward.

pure1  :: a -> f a
pure2  :: a ->    g a
pure   :: a -> f (g a)
pure a = pure1 (pure2 a)

Deriving Applicative composition: apply

apply1  :: f    (a -> b) ->  f    a  -> f    b
apply2  ::    g (a -> b) ->     g a  ->    g b
apply   :: f (g (a -> b)) -> f (g a) -> f (g b)

It’s a bit convoluted to derive the composition using apply, so this time we will go with another definition.

Lax-monoidal functor

There is an equivalent way to define Applicative functor: lax-monoidal functor.

mult :: (f a, f b) -> f (a, b)

-- here we show one can be defined in terms of another
mult (fa, fb) = (pure (,)) `apply` fa `apply` fb
apply fab fa  = fmap ($) (mult fab fa)

Deriving Applicative composition: mult

mult1 :: (f a, f b) -> f (a, b)
mult2 :: (g a, g b) -> g (a, b)
mult  :: (f (g a), f (g b)) -> f (g (a, b))

mult (fga, fgb) = let fgagb = mult1 (fga, fgb) -- :: f (g a, g b)
                  in fmap mult2 fgagb          -- :: f (g (a, b))

Monad

A Monad is an Applicative functor with a natural transformation named bind.

bind :: (a -> f b) -> f a -> f b

There is an alternative way to define Monad, that allows us to see the problem more clearly.

Monad defined using join

An equivalent way to define Monad is to use join.

join :: f (f a) -> f a
join ffa = bind id ffa
bind afa fa = join (fmap afa fa)

Composition of Monad using join

join1 :: f (f a) -> f a
join2 :: g (g a) -> g a
join  :: f (g (f (g a))) -> f (g a)

It is this interleaving of f and g that makes it difficult to compose two Monad.

Recommended reading

• Alejandro Serrano Mena on Why Functors and Applicatives Compose but Monads Don’t

The talk that inspired today’s cat-talk.

• adit.io: Lenses In Pictures

Visually explanation of functor composition.

• Typeclassopedia - HaskellWiki

Encyclopedia for common constructs like Functor, Applicative, Monad.

• Applicative Functors | Bartosz Milewski’s Programming Cafe

Equivalent ways to define Applicative Functors.