haskellmonadsfree-monad# Visualizing the Free Monad

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!

Solution

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`

- What is contributed by

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 Gabriella 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 whichever `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.")

- Comparing lists in Haskell
- Is there a non-identity monad morphism M ~> M that is monadically natural in M?
- Problem with loading module ‘Distribution.Simple’
- Improving efficiency in Stirling numbers calculation
- Does sequencing an infinite list of IO actions by definition result in a never-ending action? Or is there a way to bail out?
- How to call pgQuery from postgresql-query?
- How to avoid whitespace after a tag (link) in Hamlet templates?
- Understanding type-directed resolution in Haskell with existential types
- Why is seq bad?
- Understanding bind function in Haskell
- How to create route that will trigger on any path in Servant?
- How do I use a global state in WAI middleware?
- nixos 23.11 cabal install mysql-simple problem - "Missing (or bad) C libraries"
- Is there a way to kill all forked threads in a GHCi session without restarting it?
- Why can an invalid list expression such as 2:1 be assigned to a variable, but not printed?
- Iterate over a type level list and call a function based on each type in the list
- How does this solution of Project Euler Problem 27 in the Haskell Wiki work?
- Why `Monad` is required to use `pure`?
- Can't do partial function definitions in GHCi
- recommended way to convert Double -> Float in Haskell
- Haskell profiling understanding cost centre summary for anonymous lambda
- Why is Haskell fully declarative?
- GHC Generating Redundant Core Operations
- Question about Event firing in reflex-frp
- Using Haskell's "Maybe", type declarations
- How can I elegantly invert a Map's keys and values?
- Why there is no output for wrapped IO in Haskell?
- What are the definitions of Weather and Memory in xmobar repo?
- Serializing a Data.Text value to a ByteString without unnecessary \NUL bytes
- Using Haskell with VS Code