> The effect systems using free monads seem to keep applying a functor to itself an unlimited amount of times and I really didn't get it.
I can't help with the "effect systems" side of this, but I might be able to elucidate some of the recursive functor thing for you.
Suppose you've got a binary tree structure. In something like Haskell, you might model it like so:
data BinaryTree t where
InternalNode :: (BinaryTree t, BinaryTree t) -> BinaryTree t
LeafNode :: t -> BinaryTree t
(I could have written this in Java, but I can't bear writing subclasses to make up for a lack of sum types. It looks pretty much the same in Rust, plus Boxes. In C++, this would be `class Node { std::variant* , Node* >> data; }`... or something like that.)
When I put a bunch of these nodes together, I get a binary tree. But maybe I want to store these nodes in a database, and I need to store them as rows in a table, where a node's children are given by foreign keys into the same table. I could write a whole new type for this...
data RowNode t where
InternalRow :: (Integer, Integer) -> RowNode t
LeafRow :: t -> RowNode t
... but now I've duplicated the structure just to change the references. What if we take the child references as another type parameter?
data NodeF t child where
Internal :: (child, child) -> NodeF t child
Leaf :: t -> NodeF t child
type RowNode t = NodeF t Integer
data BinaryTree t where
MkBinaryTree :: (NodeF t (BinaryTree t)) -> BinaryTree t
Now I get my recursive trees and my flat tables out of the same basic "tile". NodeF is a functor (although I haven't said why, yet), and BinaryTree applies it to itself recursively (using Box as pointer indirection).
The MkBinaryTree constructor isn't doing anything special. It's just wrapping the given node into a new type, like how pointer indirection is necessary in C++ or Rust to avoid infinite-sized types. Similarly, Haskell doesn't allow recursive type aliases.
That's really the key point behind the recursive functors. We're extracting the "child" type out as a type parameter, and plugging it back in recursively to get our unbounded-depth tree back. Everything after this point is about what free monads add to this, which might be less interesting -- but I've already written it now, so whoops...
Why is NodeF a functor? I can write a function that takes a `NodeF t child` and a function from `child` to `stepchild`, swap the children out using the function, and produce a new `NodeF t stepchild`. That's just "fmap" -- and that's why we stuck an `F` on the name "NodeF", as a kind of Hungarian notation.
instance Functor (NodeF t) where
fmap f (Internal x y) = (Internal (f x) (f y)
fmap f (Leaf t) = (Leaf t)
Now, if I pull a random definition of `Free f` from the webs...
-- adapted from https://stackoverflow.com/a/13357359/159876
data Free f a where
Pure :: a -> Free f a
Roll :: (f (Free f a)) -> Free f a
... and inline our `NodeF t` functor into it...
data FreeNodeF t child where
Pure :: child -> Free t child
Roll :: (NodeF t (FreeNodeF t child)) -> FreeNodeF t child
The "Roll" variant is essentially the same as our BinaryTree construction, in that we can construct arbitrary binary trees with concrete values. The "Pure" variant lets us end the tree, but ending in a "child" instead of a leaf value. It'll be helpful to think of this more as a "pause" than as a "stop".
If the `child` is itself a `FreeNodeF t grandchild`, then the whole structure is a `FreeNodeF t (FreeNodeF t grandchild)`, and the canonical thing monads let us do is flatten the nested structure into a `FreeNodeF t grandchild`. In other words, we roll the `Pure` subtree over into the other variant.
The "impure" computation our `FreeNodeF` describes is essentially a branching computation. At each step, we can take a value and replace it with a tree of other values. The next step is performed on each of the values in the new subtree, and so on. At any point, each path can terminate in a final `t` value; but other paths might still keep going.
Essentially, we've structured our computation itself into a binary tree. The upshot is that the free monad lets you structure your computation into any template given by an appropriate functor. The paths through your structure trace the steps over time taken by your program.