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:
- "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.
- 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.")
