module RandomThoughts where

Free The Monads!!

There are plenty of monad tutorials out there, to the point it’s become a meme within the functional programming community whenever a new one appears. Monads are like burritos, you’d say. But it’s much less common to spot free monad tutorials in the wild, isn’t it? Is monad slavery so common that their freedom is seen as taboo, perhaps? Who knows.

In any case, what is a free monad? A free monad is an abstraction over the effects of a monad; that is, a ‘free’ monad is a monad that does not define any particular structure (such as Maybe’s short-circuiting, Reader’s context-reading, Writer’s log-tracking, Cont’s mind-bending sorcery… ahem, you get the point). A free monad emerges as the natural abstraction when we don’t care about what a monad does, only that it is a monad.

It might help to realise that, in the exact same way, List is a free monoid. Remember that a monoid is a structure that allows combining elements (a -> a -> a), as well as having a neutral element or identity. A list is a free monoid because it allows ‘combining’ elements (concatenating lists) without performing any interpretation of what the values actually mean, unlike, for example, the number addition monoid. Do note that the identity element, the empty list in the case of List, will get consumed (as in how any list A is equal to A ++ [] and [] ++ A).

Let’s suppose we want to define a monadic interface for an abstract database; our database has just two operations: GetName (:: User -> String) and SetName (:: User -> String -> ()). These are pretty general operations and quite self-explanatory; they don’t represent any actual database, just an example. A monadic interface would provide us a type constructor, ‘Database’, and the operations:

getName :: User -> Database String
setName :: User -> String -> Database ()

along with a Monad instance for the Database type.

Let’s play a game now: we’ll pretend not to know what free monads are, and we’ll try to reinvent them ourselves. If you don’t know what free monads are, then congratulations! You’re already ahead in the game. I think we can agree that, the most natural way to define ‘Database’, is by describing what a Database computation can be:

data Database a
    = Final a
    | GetName User (String -> Database a)
    | SetName User String (() -> Database a)

Alright, we have the type, and a very obvious implementation for ‘return’ (it’s literally just Final, as per definition). How do we define bind, though? It gets a little tricky, but it’s not too hard to see how it all boils down to fmap. Let me explain. (ma >>= a2mb) can easily be defined if ‘ma’ is a Final; simply pass the final result into the function ‘a2mb’ to get the next computation.

But what if ‘a’ isn’t Final, but, say, GetName? Then that means we need to perform a GetName effect first. This means the returned operation must still be a GetName in the outermost layer, since that’s the first step we have to perform. So what changes? Well, the continuation! Suppose our original GetName has a continuation ‘p’ (with p :: String -> Database a). We want to compose it with the next step ‘f’ (with f :: a -> Database b), into a new continuation of type String -> Database b. If we ignore the String argument, this composition looks just like bind.

Now if your instinct is to call bind recursively, you’d be totally right. Notice an important detail: the recursive call to bind is done not on the original effect ‘a’, but on its continuation result. This means the recursive calls are getting to a base case eventually, so there’s no issue there.

Putting this all together, the implementation looks something like this:

return = Final
(Final a) >>= a2mb = a2mb a
(GetName user r2ma) >>= f =
    GetName user (\r -> r2ma r >>= a2mb)
(SetName user name r2ma) >>= f =
    SetName user name (\r -> r2ma r >>= a2mb)

We also need to define the ‘getName’ and ‘setName’ effects directly, as originally described. This isn’t too hard; ‘getName’ is literally just ‘GetName’, but whose continuation does nothing interesting.

getName user = GetName user (\string -> Final string)

notice the continuation simply wraps the result into Final (we could omit the whole lambda, but I left it for clarity). Likewise for the other effects,

setName user name = SetName user name (\() -> Final ())

If these definitions make total sense to you, then you’ve already understood what free monads are. This is it. Well, almost. We can still abstract this structure further; notice all the repeated code? Every effect’s case looks the exact same, aside from the specific effect (GetName, SetName) and its arguments (user, name). The rest is the exact same, and it makes sense; we don’t care what the effect is, since the only thing we do is change what happens after that effect is performed.

To take advantage of this, we can define an even more abstract structure: a generic free monad. One that doesn’t have hard-coded effects, but instead allows being used with any ‘effect set’. But what should the effects be? A list? A tuple? To figure it out, we’ll ask ourselves a key question: what structure did we need SetName and GetName to have, in order to implement bind earlier? Mapping the continuation; that’s what we needed: to change the continuation, allowing us to sequence it with the next step. So let’s try defining an ‘effect functor’, which only described what effects are possible:

data DatabaseEffect a
    = GetName User (String -> a)
    | SetName User String (() -> a)
    deriving Functor

Notice this datatype doesn’t have recursion at all; it only says ‘a Database-dependent value of type ‘a’ can either be a GetName requirement, providing a user and requiring a string, or a SetName requirement, providing both user and string, but expecting nothing (unit). That way, if we have a function that returns some ‘a’ but requires a username, and we also have a specific user, we can wrap that into a ‘DatabaseEffect a’. Also notice we derive a Functor out of it in order to implement bind, as we realised earlier.

Now we can define the Free datatype itself:

data Free ef a
    = Final a
    | Effect (ef (Free ef a))

If you’ve been following the explanation so far, this shouldn’t be too surprising, although the second case might be a little tricky. Here, ‘ef’ is our ‘effect functor’, so the Effect case encodes having another computation (Free ef a; the next step) but wrapped inside an effect (ef), meaning the effect must be performed before the next step can be accessed.

Implementing the monadic interface, at this point, is rather trivial; we’ve already seen how it’s done:

    return = Final
    (Final a) >>= a2mb = a2mb a
    (Effect ef_ma) >>= a2mb = Effect (fmap ma2mb ef_ma) -- ef_ma :: ef (Free ef a)
        where ma2mb ma = ma >>= a2mb -- ma2mb :: Free ef a -> Free ef b

You might be wondering why we’re mapping the continuation results directly now, ignoring their arguments; this is because the Functor instance of ‘ef’ already maps the effect's immediate result, so we don’t have to do it manually. To see why, imagine that some operations returned multiple results in a curried way, for example:

...
| GetUserData user (Bio -> Followers -> Following -> a)

Then this effect would have a different ‘continuation’ structure, meaning we’d need to bind it in a different way, something of the form:

(GetUserData user rs2a) >>= a2mb = GetUserData user (\bio followers following -> rs2a bio followers following >>= a2mb)

which wouldn’t allow us to abstract them all into the same function.

This also shows that the structure of the effect functor is quite flexible, so long as all occurrences of ‘a’, the wrapped type, appear as a result (Functor instances cannot be derived otherwise, but that’s a lesson for another day). For example, the following effect functor is also valid:

data DatabaseEffect’ a
    = GetName User (String -> a)
    | SetName User String (() -> a)
    | Panic Error

Notice how, in the third case, there is no continuation at all; we’re telling the program to simply panic and abort, providing only an error message. It is also possible to include more than one continuation, leading to some interesting effect functors.

As a bonus, we also get a generic definition for direct effects. Earlier, we defined ‘setName’ and ‘getName’ mechanically; we can abstract those definitions now. First let’s adapt the earlier definitions:

getName user = effect $ GetName user id
setName user name = effect $ SetName user name id

Notice we’re passing ‘id’ as the continuations; this means the effect will simply return its own result. Now we can see the type of ‘effect’ is ‘ef a -> Effect ef a’. This can be easily implemented as well, like so:

effect ef_a = Effect (fmap a2ma ef_a)
    where a2ma = Final

Great, so now we can write do-blocks using database operations and sequence them easily, without worrying about how they’re carried out in practice. But, how do we actually carry them out? That’s when interpreters come into play. An interpreter, put simply, is a function that allows us to read the computation, effect by effect, and run them in some particular way. For example, this could be a possible interpreter for our DatabaseEffect’ computations:

fakedb :: Free DatabaseEffect’ a -> Writer String (Either Error a)
fakedb (Final a) = return (Right a)
fakedb (Effect (Panic err)) = return (Left err)
fakedb (Effect (GetName user cont)) = do
    tell “GetName executed! Replying with Fake!”
    fakedb (cont “Fake”) -- run the next steps with “Fake” as the result
fakedb (Effect (SetName user name cont)) = do
    tell $ “SetName executed! Name of a user changed to “ ++ name
    fakedb (cont ())

Now I’m not going to explain Writer or Either, as I assume, given you’re reading this, you already know them very well. Overall, what this silly interpreter does is run the computation in a mock environment with no real database and log what it does (optionally returning an error if the computation uses Panic).

In this explanation, I intentionally left out category-theory insights, such as why the name ‘free’. That one is not that hard, actually; these monads are called ‘free’ because they are free to be interpreted in any way. As mentioned at the beginning, they don’t enforce any concrete reduction on their effects. As for the rest, I think category theory is definitely worth exploring, but I’d be lying if I claimed to understand even a single word from it.