What monads can be expressed as Free over some functor?

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?

Solution

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

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
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.