Visualizing the Free Monad

Question

I think I have rough idea of what the free monad is, but I would like to have a better way to visualize it.

It makes sense that free magmas are just binary trees because that's as "general" as you can be without losing any information.

Similarly, it makes sense that free monoids are just lists, because the order of operations doesn't matter. There is now a redundancy in the "binary tree", so you can just flatten it, if that makes sense.

It makes sense that free groups kind of look like fractals, for a similar reason: https://en.wikipedia.org/wiki/Cayley_graph#/media/File:Cayley_graph_of_F2.svg and to get other groups, we just identify different elements of the group as being the "same" and we get other groups.

How should I be visualizing the free monad? Right now, I just think of it as the most general abstract syntax tree that you can imagine. Is that essentially it? Or am I oversimplifying it?

Also, similarly, what do we lose in going from a free monad to a list or other monads? What are we identifying to be the "same"?

I appreciate all comments that shed light into this. Thanks!

Answer 1

Right now, I just think of [the free monad] as the most general abstract syntax tree that you can imagine. Is that essentially it? Or am I oversimplifying it?

You're oversimplifying it:

1. "Free monad" is short for "the free monad over a specific functor" or the Free f a data type, which in reality is a different free monad for each choice of f.
2. There is no one general structure that all free monads have. Their structure breaks down into:
   • What is contributed by Free itself
   • What is contributed by different choices for f

But let's take a different approach. I learned free monads by first studying the closely related operational monad instead, which has a more uniform, easier-to-visualize structure. I highly recommend you study that from the link itself.

The simplest way to define the operational monad is like this:

{-# LANGUAGE GADTs #-}

data Program instr a where
  Return :: a -> Program instr a
  Bind :: instr x                  -- an "instruction" with result type `x`
       -> (x -> Program instr a)   -- function that computes rest of program
       -> Program instr a          -- a program with result type `a`

...where the instr type parameter represents the "instruction" type of the monad, usually a GADT. For example (taken from the link):

data StackInstruction a where
    Pop  :: StackInstruction Int
    Push :: Int -> StackInstruction ()

So a Program in the operational monad, informally, I'd visualize it as a "dynamic list" of instructions, where the result produced by the execution of any instruction is used as input to the function that decides what the "tail" of the "instruction list" is. The Bind constructor pairs an instruction with a "tail chooser" function.

Many free monads can also be visualized in similar terms—you can say that the functor chosen for a given a free monad serves as its "instruction set." But with free monads the "tails" or "children" of the "instruction" are managed by the Functor itself. So a simple example (taken from Gabriel González's popular blog entry on the topic):

data Free f r = Free (f (Free f r)) | Pure r

-- The `next` parameter represents the "tails" of the computation.
data Toy b next =
    Output b next
  | Bell next
  | Done

instance Functor (Toy b) where
  fmap f (Output b next) = Output b (f next)
  fmap f (Bell next) = Bell (f next)
  fmap _ Done = Done

While in the operational monad the function used to generate the "tail" belongs to the Program type (in the Bind constructor), in free monads the tails belong to the "instruction"/Functor type. This allows the free monad's "instructions" (an analogy that is now breaking down) to have a single "tail" (like Output or Bell), zero tails (like Done) or multiple tails if you so chose to. Or, in another common pattern, the next parameter can be the result type of an embedded function:

data Terminal a next = 
    PutStrLn String next
  | GetLine (String -> next)  -- can't access the next "instruction" unless
                              -- you supply a `String`.

instance Functor Terminal where
    fmap f (PutStrLn str next) = PutStrLn str (f next)
    fmap f (GetLine g) = GetLine (fmap f g)

This, incidentally, is an objection I've long had to people who refer to free or operational monads as "syntax trees"—practical use of them requires that "children" of a node be opaquely hidden inside a function. You generally can't fully inspect this "tree"!

So really, when you get down to it, how to visualize a free monad comes down entirely to the structure of the Functor that you use to parametrize it. Some look like lists, some look like trees, and some look like "opaque trees" with functions as nodes. (Somebody once responded to my objection above with a line like "a function is a tree node with as many children as there are possible arguments.")