Flavours of free applicative functors
Published on
Six months ago Tom Ellis wrote the article Towards Free Applicatives, where he described his implementation of a free applicative functor. In the reddit discussion of that article a few more implementations were suggested.
In this article I would like to look in more detail how these implementations work and how they differ from each other.
The implementations are rewritten in a common style where possible, to highlight the differences and similarities. Since a picture is worth a thousand words, for each implementation there’s a diagram showing how a simple applicative expression f <$> lift ax <*> lift ay <*> lift az
is represented.
Notational conventions
x
,y
,z
,f
— simple (non-functorial) valuesax
,ay
,az
— values of the base functor typetx
,ty
,tz
— values of the free applicative functor type
On the diagrams
F
— base functorTx
,Ty
,Tz
— inner types of functorial values (e.g.ax
has typeF Tx
). The functionf
has typeTx -> Ty -> Tz -> Tr
.- A square denotes unit (i.e.
()
) as a type, term and pattern.
Ørjan Johansen’s free applicative
data Free f a where
Pure :: a -> Free f a
Ap :: Free f (a -> b) -> f a -> Free f b
instance Functor f => Functor (Free f) where
fmap f (Pure x) = Pure $ f x
fmap f (Ap tx ay) = Ap ((f .) <$> tx) ay
instance Functor f => Applicative (Free f) where
pure = Pure
<*> Pure y = fmap ($ y) tx
tx <*> Ap ty az = Ap ((.) <$> tx <*> ty) az
tx
lift :: f a -> Free f a
= Ap (Pure id)
lift
lower :: Applicative f => Free f a -> f a
Pure x) = pure x
lower (Ap tx ay) = lower tx <*> ay lower (
The tree grows to the left. This can be easily seen on the diagram, and follows from the fact that the first argument of Ap
is a free applicative itself and the second is not. (How the tree grows depends, obviously, on the order of Ap
’s arguments. The convention here is that Ap
’s arguments are in the applicative order, so that we can meaningfully talk about the tree’s associativity.)
<*>
pattern-matches on its right argument, effectively re-associating the tree to the left.
Note that Free f a
is an applicative functor regardless of f
. It stores f
-values in the tree without changes. We’ll see later that this is not always the case.
Twan van Laarhoven’s free applicative
data Free f a where
Pure :: a -> Free f a
Ap :: Free f (a -> b) -> f a -> Free f b
instance Functor (Free f) where
fmap f (Pure x) = Pure $ f x
fmap f (Ap tx ay) = Ap ((f .) <$> tx) ay
instance Applicative (Free f) where
pure = Pure
Pure f <*> tx = fmap f tx
Ap tx ay <*> tz = Ap (flip <$> tx <*> tz) ay
lift :: f a -> Free f a
= Ap (Pure id)
lift
lower :: Applicative f => Free f a -> f a
Pure x) = pure x
lower (Ap tx ay) = flip id <$> ay <*> lower tx lower (
This is a variation of Ørjan’s implementation. As can be seen from the diagrams, the only difference is that it stores the values in the opposite order, and modifies the function to accept them in that order.
As in Ørjan’s implementation, the tree grows to the left, but <*>
now pattern-matches on its left argument, in order to push its right argument to the leftmost position in the tree.
The way <*>
does pattern matching directly affects its algorithmic complexity. Ørjan’s implementation is linear in the size of its right argument and thus works better with left-associated applicative expressions. Twan’s version is dual: it is linear in the size of its left argument and works better with right-associated expressions. In both cases, unfortunate nesting increases complexity from linear to quadratic.
Also pay attention to the lower
function. It has to take care of the effects — the right subtree must be «executed» before the left subtree in order to restore the original value faithfully.
Paolo Capriotti’s free applicative
data Free f a where
Pure :: a -> Free f a
Ap :: f (a -> b) -> Free f a -> Free f b
instance Functor f => Functor (Free f) where
fmap f (Pure x) = Pure $ f x
fmap f (Ap ax ty) = Ap (fmap (f.) ax) ty
instance Functor f => Applicative (Free f) where
pure = Pure
Pure f <*> tx = fmap f tx
Ap ax ty <*> tz = Ap (fmap uncurry ax) ((,) <$> ty <*> tz)
lift :: Functor f => f a -> Free f a
= Ap (const <$> ax) (Pure ())
lift ax
lower :: Applicative f => Free f a -> f a
Pure x) = pure x
lower (Ap ax ty) = ax <*> lower ty lower (
The diagram looks more complicated here. The first thing to notice is that the tree here grows to the right, unlike in the previous versions. The actual application of our f
function happens now near the top of the tree rather than at the bottom. To make that possible, the function has to be converted to the uncurried form.
All left nodes except the topmost one are functions (wrapped in the base functor). All they do is take a nested tuple of the arguments downstream and add their own value to that tuple. The topmost left node already knows the final required argument, ax
, and simply applies the uncurried function to the tuple.
The functorial values are stored in a modified form, which requires f
to be an actual Functor
. (But note that any f
can be turned into a functor using Yoneda.)
Tom Ellis’s free applicative
The code here is quite different from the previous versions, so I decided to reproduce it verbatim (except the lift
and lower
functions, which I’ve added myself).
data ChainA f a b = Single (f (a -> b)) | forall c. Many (f (c -> b)) (ChainA f a c)
instance Functor f => Functor (ChainA f a) where
fmap f (Single t) = Single (fmap (f .) t)
fmap f (Many g v) = Many (fmap (f .) g) v
chain :: ChainA f b c -> ChainA f a b -> ChainA f a c
Single t) v = Many t v
chain (Many t ts) v = Many t (chain ts v)
chain (
data FreeA f a = Pure a | ChainA (ChainA f () a)
instance Functor f => Functor (FreeA f) where
fmap f (Pure a) = Pure (f a)
fmap f (ChainA a) = ChainA (fmap f a)
instance Functor f => Applicative (FreeA f) where
pure = Pure
Pure f <*> g = fmap f g
<*> Pure g = fmap ($ g) f
f ChainA f <*> ChainA g = ChainA $ chain (pullUnit f) g
pullUnit :: Functor f => ChainA f () (b -> c) -> ChainA f b c
= removeUnit . pull
pullUnit
pass :: Functor f => ChainA f a b -> ChainA f (a,c) (b,c)
Single t) = Single (fmap (\f -> \(a,c) -> (f a, c)) t)
pass (Many t ts) = Many (fmap (\f -> \(a,c) -> (f a, c)) t) (pass ts)
pass (
pull :: Functor f => ChainA f a (b -> c) -> ChainA f (a,b) c
Single t) = Single (fmap uncurry t)
pull (Many t ts) = Many (fmap uncurry t) (pass ts)
pull (
removeUnit :: Functor f => ChainA f ((), a) b -> ChainA f a b
Single t) = Single (fmap (\f -> \a -> f ((),a)) t)
removeUnit (Many t ts) = Many t (removeUnit ts)
removeUnit (
lift :: Functor f => f a -> FreeA f a
= ChainA $ Single $ const <$> ax
lift ax
lower :: Applicative f => FreeA f a -> f a
Pure x) = pure x
lower (ChainA chain) = lowerChain chain <*> pure ()
lower (where
lowerChain :: Applicative f => ChainA f x y -> f (x -> y)
Single ax) = ax
lowerChain (Many ax ty) = (.) <$> ax <*> lowerChain ty lowerChain (
Despite the superficial dissimilarity of the code, this is really a variation on Paolo’s implementation. The only difference is that unit is not passed as a part of the nested tuples. Two-level types and auxiliary functions are really just the cost of eliminating that unit.
Which one to use?
The free package currently uses the Twan’s version, which is the reason of the reverse effect that I mentioned in the previous article. Edward Kmett points out that the reason for choosing Twan’s implementation is that you can see the «next instruction» in O(1) when walking left to right, which is most common.
So start with that one, but also look at your problem (how exactly you are going to analyze the free applicative) and see if any of the alternatives fit better.