Functorial Blog

A blog about functional programming

RSS Feed

© Phil Freeman 2010-2017

FreeAp is a Comonad

by Phil Freeman on 2017/07/01

While thinking about comonads as spaces and Day convolution, I realized an interesting thing. The free applicative functor generated by a comonad f is also a comonad.

The free applicative can be defined in a few different ways, but I like to define it like this:

data FreeApplicative f a = Pure a | Free (Day f (FreeApplicative f) a)

Here, Day is taken from my purescript-day package. I think this presentation makes it easy to understand the free applicative, since it is just a Day convolution of a finite number of copies of f. It also makes it simple to define various operations like hoistFreeAp.

If we refactor this slightly to use a Coproduct, then a Comonad instance can even be derived:

newtype FreeApplicative f a = FreeApplicative (Coproduct Identity (Day f (FreeApplicative f)) a)

derive newtype instance functorFreeApplicative :: Functor f => Functor (FreeApplicative f)
derive newtype instance extendFreeApplicative :: Extend f => Extend (FreeApplicative f)
derive newtype instance comonadFreeApplicative :: Comonad f => Comonad (FreeApplicative f)

This works since Identity is a comonad, and Coproduct and Day both preserve comonads.

In the comonads as spaces approach to user interfaces, the free applicative gives a way to build a UI for a finite list of subcomponents, just like Day gives us a way to compose two subcomponents.

Unfortunately, FreeAp isn't a Comonad transformer. The problem is that we would not be able to handle the Pure case if we tried to lower a FreeAp w to a w.

However, we can construct a ComonadTrans instance if we restrict ourselves to a Day convolution of a non-zero number of copies of f. Instead of the free Applicative, this gives us the free Apply:

newtype FreeApplicative f a = FreeApplicative (Coproduct Identity (FreeApply f) a)

derive newtype instance functorFreeApplicative :: Functor f => Functor (FreeApplicative f)
derive newtype instance extendFreeApplicative :: Extend f => Extend (FreeApplicative f)
derive newtype instance comonadFreeApplicative :: Comonad f => Comonad (FreeApplicative f)

newtype FreeApply f a = FreeApply (Day f (FreeApplicative f) a)

derive newtype instance functorFreeApply :: Functor f => Functor (FreeApply f)
derive newtype instance extendFreeApply :: Extend f => Extend (FreeApply f)
derive newtype instance comonadFreeApply :: Comonad f => Comonad (FreeApply f)

Now, we can write a ComonadTrans instance for FreeApply which keeps the first w in a non-empty collection of ws, and extracts the focus from the rest.

instance comonadTransFreeApply :: ComonadTrans FreeApply where
  lower (FreeApply d) = runDay (\f w fa -> map (\x -> f x (extract fa)) w) d