What monads can be expressed as Free over some functor?

Question

The documentation for Free says:

A number of common monads arise as free monads,

• Given data Empty a, Free Empty is isomorphic to the Identity monad.
• Free Maybe can be used to model a partiality monad where each layer represents running the computation for a while longer.

What other monads are expressible using Free?

I could think only of one more: I believe Free (Const e) is isomorphic to Either e.

Edit: What monads are not expressible using Free and why?

Answer 1

Almost all of them (up to issues involving looping and mfix) but not Cont.

Consider the State monad

newtype State s a = State (s -> (a,s)) 

does not look anything like a free monad... but think about State in terms of how you use it

get :: m s --or equivalently (s -> m a) -> m a set :: s -> m () --or (s,m a) -> m a runState :: m a -> s -> (a,s) 

we can design a free monad with this interface by listing the operations as constructors

data StateF s a   = Get (s -> a) | Set s a deriving Functor 

then we have

type State s a = Free (StateF s) a 

with

get = Impure (Get Pure) set x = Impure (Set x (Pure ()) 

and we just need a way to use it

runState (Pure a) s = (a,s) runState (Impure (Get f)) s = runState (f s) s runState (Impure (Set s next)) _ = runState next s 

you can do this construction with most monads. Like the maybe/partiality monad is defined by

stop :: m a maybe :: b -> (a -> b) -> m a -> b 

the rule is, we treat each of the functions that end in m x for some x as a constructor in the functor, and the other functions are ways of running the resulting free monad. In this case

data StopF a = StopF deriving Functor  maybe _ f (Pure a)      = f a maybe b _ (Impure Stop) = b 

why is this cool? Well a few things

1. The free monad gives you a piece of data that you can think of as being an AST for the monadic code. You can write functions that operate on this data which is really useful for DSLs
2. Functors compose, which means breaking down your monads like this makes them semi composeable. In particular, given two functors which share an algebra (an algebra is essentially just a function f a -> a for some a when f is a functor), the composition also has that algebra.

Functor composition is just We can combine functors in several ways, most of which preserve that algebra. In this case we want not the composition of functors (f (g (x))) but the functor coproduct. Functors add

data f :+: g a = Inl (f a) | Inr (g a)   instance (Functor f, Functor g) => Functor (f :+: g) where   fmap f (Inl x) = Inl (fmap f x)   fmap f (Inr x) = Inr (fmap f x)  compAlg :: (f a -> a) -> (g a -> a) -> f :+: g a -> a compAlg f _ (Inl x) = f x compAlf _ g (Inr x) = g x 

also free monads preserve algebras

freeAlg :: (f a -> a) -> Free f a -> a freeAlg _ (Pure a) = a freeAlg f (Impure x) = f $ fmap (freeAlg f) x 

In Wouter Swierstra's famous paper Data Types A La Carte this is used to great effect. A simple example from that paper is the calculator. Which we will take a monadic take on new to this post. Given the algebra

class Calculator f where  eval :: f Integer -> Integer 

we can think of various instances

data Mult a = Mult a a deriving Functor instance Calculator Mult where   eval (Mult a b) = a*b  data Add a = Add a a deriving Functor instance Calculator Add where   eval (Add a b) = a+b  data Neg a = Neg a deriving Functor instance Calculator Neg where   eval (Neg a) = negate a  instance Calculator (Const Integer) where   eval (Const a) = a  data Signum a = Signum a deriving Functor instance Calculator Signum where   eval (Signum a) = signum a  data Abs a = Abs a deriving Functor instance Calculator Abs where   eval (Abs a) = abs a 

and the most important

instance (Calculator f, Calculator g) => Calculator (f :+: g) where    eval = compAlg eval 

you can define the numeric monad

newtype Numerical a = Numerical (         Free (Mult          :+: Add          :+: Neg          :+: Const Integer          :+: Signum         :+: Abs) a deriving (Functor, Monad) 

and you can then define

 instance Num (Numerical a) 

which might be totally useless, but I find very cool. It does let you define other things like

 class Pretty f where     pretty :: f String -> String   instance Pretty Mult where     pretty (Mult a b) = a ++ "*" ++ b 

and similar for all the rest of them.

It is a useful design stategy: list the things you want your monad to do ==> define functors for each operation ==> figure out what some of its algebras should be ==> define those functors for each operation ==> make it fast.

Making it fast is hard, but we have some tricks. Trick 1 is to just wrap your free monad in Codensity (the "go faster button") but when that doesn't work you want to get rid of the free representation. Remember when we had

runState (Pure a) s = (a,s) runState (Impure (Get f)) s = runState (f s) s runState (Impure (Set s next)) _ = runState next s 

well, this is a function from Free StateF a to s -> (a,s) just using the result type as our definition for state seems reasonable...but how do we define the operations? In this case, you know the answer, but one way of deriving it would be to think in terms of what Conal Elliott calls type class morphisms. You want

runState (return a) = return a runState (x >>= f) = (runState x) >>= (runState f) runState (set x) = set x runState get = get 

which makes it pretty easy

runState (return a) = (Pure a) = \s -> (a,s)  runState (set x)     = runState (Impure (Set x (Pure ())))     = \_ -> runState (Pure ()) x    = \_ -> (\s -> (a,s)) x    = \_ -> (a,x)  runState get   = runState (Impure (Get Pure))   = \s -> runState (Pure s) s   = \s -> (s,s) 

which is pretty darn helpful. Deriving >>= in this way can be tough, and I won't include it here, but the others of these are exactly the definitions you would expect.

Answer 2

To answer the question as it is stated, most of the familiar monads that you didn't mention in the question are not themselves free monads. Philip JF's answer alludes to how you can relate a given monad to a new, free monad, but the new monad will be "bigger": it has more distinct values than the original monad. For example the real State s monad satisfies get >>= put = return (), but the free monad on StateF does not. As a free monad, it does not satisfy extra equations by definition; that is the very notion of freeness.

I'll show that the Reader r, Writer w and State s monads are not free except under special conditions on r/w/s.

Let me introduce some terminology. If m is a monad then we call any value of a type m a an (m-)action. We call an m-action trivial if it is equal to return x for some x; otherwise we call it nontrivial.

If m = Free f is any free monad on a functor f, then m admits a monad homomorphism to Maybe. This is because Free is functorial in its argument f and Maybe = Free (Const ()) where Const () is the terminal object in the category of functors. Concretely, this homomorphism can be written

toMaybe :: Free f a -> Maybe a toMaybe (Pure a) = Just a toMaybe (Impure _) = Nothing 

Because toMaybe is a monad homomorphism, it in particular satisfies toMaybe (v >> w) = toMaybe v >> toMaybe w for any m-actions v and w. Now observe that toMaybe sends trivial m-actions to trivial Maybe-actions and nontrivial m-actions to the nontrivial Maybe-action Nothing. Now Maybe has the property that >>ing a nontrivial action with any action, in either order, yields a nontrivial action (Nothing >> w = v >> Nothing = Nothing); so the same is true for m, since toMaybe is a monad homomorphism that preserves (non)triviality.

(If you prefer, you could also verify this directly from the formula for >> for a free monad.)

To show that a particular monad m is not isomorphic to any free monad, then, it suffices to find m-actions v and w such that at least one of v and w is not trivial but v >> w is trivial.

Reader r satisfies v >> w = w, so we just need to pick w = return () and any nontrivial action v, which exists as long as r has at least two values (then ask is nonconstant, i.e., nontrivial).

For Writer w, suppose there is an invertible element k :: w other than the identity. Let kinv :: w be its inverse. Then tell k >> tell kinv = return (), but tell k and tell kinv are nontrivial. Any nontrivial group (e.g. integers under addition) has such an element k. I presume that the free monads of the form Writer w are only those for which the monoid w is itself free, i.e., w = [a], Writer w ~ Free ((,) a).

For State s, similarly if s admits any nontrivial automorphism f :: s -> s with inverse finv :: s -> s, then modify f >> modify finv = return (). Any type s with at least two elements and decidable equality has such automorphisms.