Notes on free monads

Free monads are things that I’ve heard about, and feel like I mostly get, but I haven’t had an opportunity to use them in anger to really cement the intuition. So I’m writing down a bunch of related thoughts and intuitions that have helped, to refer back to in lieu of experience.

A tree with f-shaped branches

Kmett says, “you can think of Free f a as a tree with an f-shaped branching structure.” Nate Faubion’s “Free from tree” presentation elaborates on this: plug in Pair for f and you’ve got a binary search tree (though more practically, you’d want Compose Pair Maybe to allow for trees with more than just an even number of branches at each node).

data Pair a = Pair a a

data Free f a
  = Pure a
  | Roll (f (Free f a))

type BST a = Free Pair a

tree :: BST Int
tree =
  Roll (Pair
    (Roll (Pair
      (Pure 1)
      (Pure 3)))
    (Pure 7))

Static analysis

One of the perceived benefits of expressing your program in terms of Free is that you might be able to statically analyze it (as a pure data structure), or do a “dry run”. This is true for an AST built out of operators like

data Operator a
  = Add a a
  | Sub a a
  | Mul a a
  | Neg a

But, it doesn’t seem particularly useful to wrap Operation in Free? do notation doesn’t add anything.

In the case where f in your Free f contains a continuation (f has any data constructors that take a lambda), for example

data CmdF next
  = PutLine String next
  | GetLine (String -> next)

the program would not be introspectable, and you would need to provide all your inputs up front to do a dry run. Probably obvious, but something Kovanikov notes in his talk as a “weird thing” that gets overlooked in tutorials.

Monad is to Monoid as foldFree is to foldMap

List is called the “free monoid”, and foldFree is kinda like foldMap if you squint (and use squiggly arrow ~> for natural transformations)

foldMap
  :: Monoid m
  => (a -> m)
  -> FreeMonoid a  -- aka [a]
  -> m

foldFree
  :: Monad m
  => (f ~> m)
  -> FreeMonad f
  ~> m

Preserve your data (or AST) fully intact in the Free* structure, and then plug in different a -> m or f ~> m functions to get different interpretations of it.

Performance

There is a claim that Church-encoded free monads are “fast”. From what I understand, the idea is that nested >>=’s are quadratic when using the ordinary Free type, but can be improved (to linear) when using Church encoding. There are maybe several possible Church encodings? The canonical reference is Janis Voigtländer’s “Asymptotic Improvement of Computations over Free Monads”, and then Kmett has more to say in his “Free monads for less” series.

freer

Free’s Monad instance requires a Functor constraint on f, freer somehow bypasses this using Coyoneda. See “Freer Monads, More Extensible Effects”.