Free Monads

Remember in a previous post that the Free monad can represent a tree where each node has either a branch or a label (thus inferring only leaves have labels).

When we "convert method calls into references to an ADT [we get] the Free monad. When an ADT mirrors the arguments of related functions, it is called a Church encoding. Free is named because it can be generated for free for any S[_] . For example, we could set S to be the [algebras] and generate a data structure representation of our program... In FP, an algebra takes the place of an interface in Java... This is the layer where we define all side-effecting interactions of our system." [1]

My friend, Aaron Pritzlaff, has written a small project that (apart from demonstrating interoperability) does not use any Cats nor Zio magic. 

Here, we build case classes that are all instances of Operation[A] (where the A represents the type of the operation's result). This can conveniently be lifted into a Free[F, A] (where F is now our Operation) with .liftM. 

As it happens, this creates a type of Free[ called a Suspend[ that's essentially a placeholder for the A as when we flatMap on it, the function we use is A => Free[F, A]. And we can keep doing this until we have built up a tree of Free[Operation, A]s as we promised at the beginning of this post. A shallow path represents a for comprehension that terminates early. 

The important thing to remeber is that we built a data structure that is yet to be executed.

We would execute the true with a call to ".foldMap [which] has a marketing buzzword name: MapReduce." [1] In Aaron's implementation, we just recursively call .foldMap on the Free tree we constructed. Either we'll terminate with a pure value or a Suspended node that will be mapped to a natural transformation (using the ~> function) that maps not A to B, but F[_] to G[_]. This is our interpreter and for us, G must be a monad so we can call flatMap as we pop the stack.

As we work our way back through the stack of monads calling flatMap as we go, we' re invoking those functions,  A => Free[F, A], we spoke about earlier. But note that they're acting on the Gs that our interpreter instantiated.

Although it's good to understand, the Free monad might not be your best choice according to the Cats people:

Rob Norris @tpolecat Sep 24 17:49 2020

Free is out of style but it's still great for some applications. Tagless style is much more common now for writing DSLs and APIs in general. Free is good if you really need to limit what the user can do (the algebra is exactly your data type's (i.e., F's) constructors plus Monad. No more, no less. Sometimes you want this.

The end result is easier to use than tagless because you're just dealing with data. You don't have to thread an effect parameter (typically) everywhere. So your business logic can be very concrete, which is easier for beginners I think.

Fabio Labella @SystemFw Sep 24 19:35 2020

the idea behind Free is great for implementing advanced monads like IO or Stream (which are implemented with a similar strategy even though they don't use Free literally)

Daniel Spiewak @djspiewak Sep 25 15:49 2020

I use Free for prototyping sometimes. It can be a useful tool to see how your effect algebra teases apart at a granular level without actually committing to an implementation, but it really only works for algebraic effects, and you very quickly bump up against some annoying type metaprogramming problems if you want to push it.

I think we've pretty much all learned that there are better ways of encoding effect composition than Free, and simultaneously the mocking it enables, while powerful, isn't that useful in practice... It's still a cool toy though.

[1] Functional Programming for Mortals with Cats