Extending Capability's With Free

One of the more popular topics in the Haskell ecosystem is the use of so called Free monads to create descriptive and IO free programs. However, the concept of lifting type functionality with Free is not unique to monadic computation. Let’s look a bit at the theory and practice behind the Free approach in Haskell.

Abstract Algebra

In abstract algebra the concept of free is a method of extending the functionality of an algebraic structure like a set or group to a more complex structure by dramatically enlarging it’s structure. This notion is generalized in category theory to the notion of a free functor.

Consider a category \(\mathbb{C}\) of algebraic structures (such as groups, algebras, vector spaces, etc…) and the forgetful functor \(U : \mathbb{C} \to \mathbf{Set}\) which takes algebraic structures and reduces them to sets, ignoring all operations. The free functor \(F : \mathbf{Set} \to F(X)\) is a left adjoint of \(U\), i.e. \(F\) takes sets \(X\) back into the category \(\mathbb{C}\) such that \(F \circ U = \mathbf{id}\). We refer to \(F(X)\) as the free object of the free functor \(F\).

This allows us to define the following universal property. For \(A\) an algebraic structure of \(\mathbb{C}\), let \(\phi : X -> U(A)\) be a function between sets, then we can lift \(\phi\) to a morphism \(\hat{\phi} : F(X) \to A\) of \(\mathbb{C}\) defined by the following commutative diagram.

\[ \begin{CD} X @>\phi>> U(A) \\ @VVFV @AAUA \\ F(X) @>\hat{\phi}>> A \end{CD} \]

Concrete Example

Consider a function \(f\) from a set \(X\) to the underlying set of a group \(G\). In an abuse of notation we write \(f: X \to G\) (properly it should be \(X \to U(X)\) where \(U\) is the forgetful functor \(U : \mathbf{Grp} \to \mathbf{Set}\). There exists a free functor \(F : \mathbf{Set} \to F(X)\) defined as follows. Suppose \(X\) a set of symbols and define in addition a set \(X^{-1}\) of symbols each of which corresponds to precisely one symbol in \(X\). We call the members of \(X^{-1}\) the inverses of the elements of \(X\). Let \(Y = X \cup X^{-1}\). We then define \(F(X)\) as follows.

Let a word be an element of the monoid generated by \(Y\), that is a number of symbols in \(Y\) written together. We call a word reduced if it’s inverses cancel out, i.e. \(a = ab^{-1}b = bb^{-1}a = ...\). Then \(F(X)\) is the collection of reduced words.

This allows us to define a universal property for groups. Namely that our function \(f\) extends to a group morphism \(\hat{f} : F(X) \to G\) by the following commutative diagram.

\[ \begin{CD} X @>f>> U(G) \\ @VVFV @AAUA \\ F(X) @>\hat{f}>> G \end{CD} \]

In this way we’ve defined a function \(\hat{f}\) to be a morphism of groups, thereby extending it’s functionality. Although this might seem a bit like whichcraft, it’s worth considering just how large a set \(F(X)\) we had to create in order to define that morphism. The trick to the use of free objects, is that they require building an immensely larger structure than the function was initially defined upon. Effectively, since \(X\) is in this case a basis for \(F(X)\), the free space is the generation of an algebraic structure \(F(X)\) from that basis \(X\).

Applications In Haskell

So, how does this relate to Haskell? After all, theory is great but the title of this post did relate to programming. Well, let’s look up some examples.

Monoids

A monoid is a set equipped with a single associative operation and an identity element.

The prototypical example of a monoid is a list [a]. It contains an identity element [] and an associative operation ++. It is also the prime example of the elevation of a data structure to added capability. Consider the following example.

Suppose we are building a function to validate a user’s password. We would like to be able to return some manner of error or success, and so we define a type for our potential errors.

data PasswordErr = PasswordToShort | PasswordToSimple | PasswordWellKnown
    deriving (Eq, Show)

This allows our function to return information about what exactly our password has passed.

validatePass :: Text -> Either PasswordErr Text

However, we now come to the ubiquitous user complaint, they fix one error only for another to crop up. Since they are not exclusive this is frustrating for someone trying to sign up, ideally we need a way to concatenate our errors for response. Ideally we would turn PasswordErr into a monoid to allow for concatenating errors. A first attempt might be

data PasswordErr2
    = PasswordToShort PasswordErr2
    | PasswordToSimple PasswordErr2
    | PasswordWellKnown PaswordErr
    | PaswordNoError
    deriving (Show, Eq)

instance Semigroup PasswordErr2 where
    (PasswordToShort x)   <> y = PasswordToShow (x <> y)
    (PasswordtoSimple x)  <> y = PasswordToSimple (x <> y)
    (PasswordWellKnown x) <> y = PasswordWellKnown (x <> y)
    PasswordNoError       <> y = y
    x       <> PasswordNoError = x

instance Monoid PasswordErr2 where
    mempty = PasswordNoError

Admittedly, this is very crude, and quite a lot to type out. It’s also not exactly quite clear how we would go about deconstructing errors, but in the interim it does somewhat work.

Luckily, there is an easier way! Recall that we mentioned [a] as the prototypical example of a monoid, but in so doing entirely failed to mention a key component a. Indeed, the morphism \[ \texttt{a} \to \texttt{[a]} \] is exactly a free functor from the category of sets to the category of monoids! Hence it follows that we may extend our function to work on Monoids using the original definition of PasswordErr!

validatePassword :: Text -> Either [PasswordErr] Text

Now, on the face of it this doesn’t seem like a particularly impressive achievement. In fact it is rather obvious without all the category theory talk to introduce it, however, things become much more interesting when we apply the same theory to more interesting categories.

Fixing Functors

Consider a more complicated example this time. Suppose we’re setting up a program to be used by a local DJ. We want to be able to spell out what songs are played, when breaks are taken, and when the evening comes to a close. We might write this schedule as a follows.

data Playlist a next
    = Play a next
    | Pause Int next
    | Done

We can then setup a simple program,

-- play (Song "Kraftwerk" "Computer Love"
-- pause 3
-- done
Play (Song "Kraftwerk" "Computer Love") (Pause 3 Done) :: (Playlist Song (Playlist a (Playlist b next)))

Almost immediately we run into a problem. Because the type signature mirrors our program, it’s impossible to work with the program as a generic object without also specifying the complete type. Ideally we would like some type of Playlist' type which would encapsulate a generic program.

Fortunately mathematics has been here before and can help us out. Namely there is a concept known as a fixed point, that is a point that is not moved by a function, i.e. \(f(x) = x\), moreover, in special cases, any iteration of points near the fixed point will lead to it. In limit terms if \(f_n (x) = f( f_{n-1} (x))\) then eventually for some \(y\) in a neighborhood of \(x\),

\[ \lim_{n \to \infty} f_n (y) = x. \]

We can represent this iteration in haskell as well through a recursive type,

data Fix f = Fix (f (Fix f))

At first glance these look incongruous, but consider that when f is a function f :: a -> b the above definition becomes (with some questionable syntax):

data Fix (a -> b) = Fix (a -> Fix (a -> b))

Every input of a gives the same recursive definition, i.e. \(\texttt{Fix} (f) \sim f_\infty\). Since morphisms between types can be viewed as functors and Playlist is readily a Functor:

instance Functor (Playlist x)  where
    fmap f (Play s next) = Play s (f next)
    fmap f (Pause n next) = Pause n (f next)
    fmap _ Done = Done

It’s easy to see how Fix allows us to define a fixed chain of functors, such as the following.

Fix (Play (Song "Kraftwerk" "Computer Love") (Fix Done)) :: Fix (Playlist Song)

With this type level logic in hand we can now define playlists as needed but there remains some room for improvement. For instance, although we can now define an entire playlist chain using Fix, it’s still not possible for us to write individual components of the playlist, or subsets of our playlist for reuse. To tackle this issue we have to introduce a new concept, the Free monad.

Free Monads

We now come back to the starting principle of universal properties. Namely, the problem with the setup using Fix is the inability to setup smaller sub-programs which can be bound together. That functionality is bound up within the Monad class, so our question becomes, what is the Free object which elevates a Functor to a Monod, just as [*] elevated a Set to a Monoid? Well at it’s core a Monad has two operations, bind and return. We can describe both of these in a type Free¹ as follows

data Free f r = Free (f (Free f r)) | Pure r

It’s easy to see that the return instance is setup for us.

instance (Functor f) => Monad (Free f) where
    return = Pure

However, what about the first component? It looks exactly like our definition of Fix, and indeed a binding application simply operates on the last element of the chain, changing only the type r.

    (Free x) >>= f = Free (fmap (>>= f) x)
    (Pure x) >>= f = f x

Moreover, as we would expect from a universal property we have a functor which carries a functor to the Free monad.

liftF :: (Functor f) => f a -> Free f a
liftF f = Free (fmap Pure f)

Now, monad in hand, it becomes ease itself to create sub programs. We can even define convenience functions for each of our steps, for instance:

play :: Song -> Free (Playlist Song) ()
play s = Free (Play s (Pure ())

done :: Free (Playlist a) ()
done = Free Done

-- ...

Or even simpler, we can use the Free functor liftF

pause :: Int -> Free (Playlist a) ()
pause = liftF . Pause

This gives us quite an easy way to write our playlists:

oneHitWonders :: Free (Playlist Song) ()
oneHitWonders = do
    play (Song "Len" "Steal My Sunshine")
    play (Song "Mungo Jerry" "In The Summertime")
    pause 4
    play (Song "A Flock of Seaguls" "I Ran (So Far Away)")
    done

The only thing left to do is interpret what we’ve done and maybe play our songs in the real world.

interpret :: Free (Playlist Song) a -> IO a
interpret (Free (Play s next)) = playIO s >> interpret next
interpret (Free (Pause n next)) = pauseIO n >> interpret next
interpret (Free Done) = return ()
interpret Pure r = return r

However, this is a little bit tedious, fortunately there exists an existing pattern that is applicable, folding. We can define a function for generic interpretation as

foldFree :: (Functor f, Monad m) => (forall a. f a -> m a) -> Free f a -> m a
foldFree _ (Done a) = return a
foldFree interpret (Free f) = do
    a <- interpret f
    foldFree interpret a

Putting It Into Practice

So, what’s all the buzz about? After all being able to interpret a dsl is hardly newsworthy, I mean, how is it useful? Well the joy of Free monads is that they abstract a program away from the manner in which it is used. For instance, consider writing a standard web application, you might have a database connection wrapped around IO, as well as a logger, and countless other things. We tend to write this as a large monad stack.

newtype App a = App { runApp :: ReaderT DBConn IO a }
    deriving (Functor, Monad, MonadReader DBConn) --..

getUsers :: App [User]
getUsers = do
    conn <- ask
    liftIO $ runDB conn [sql|SELECT * FROM users]

The problem with this, or rather the unfortunate thing, is the reliance on IO. The logic of the application is entirely bound up in the IO of the application. There is no way of testing it without a live database connection, and the performance of actual IO.

Amazingly however, we can accomplish the same functionality with Free monads. The idea here is to abstract away operations that could require IO as commands, that we can interpret in whatever way we might choose later on. For instance we might define

data AppFunctionality next = GetUsers ([User] -> next) | LogStr Text next
    deriving (Functor)

We can then rebuild our application using an interpreter

type App = Free AppFunctionality

getUsers :: App [User]
getUsers = liftF GetUsers

Here getUsers is effectively lifting some future [Users] type into Done, if we expand out liftF it is slightly more clear.

getUsers = Free (GetUsers Done)

Likewise we can define a logging function

log :: Text -> App ()
log = liftF . LogStr

Notably, adding context or capability to our application is as easy as defining new commands, and no where in this process have we touched IO. Our program could as easily run against predefined inputs as against a live database. Indeed for testing purposes it’s often useful to set up something like that:

interpretTest :: App a -> Writer [Text] a
interpretTest = foldFree nat
    where
        nat :: AppFunctionality a -> Writer [Text] a
        nat (GetUsers f) = return $ f [User "Bob", User "Alice"]  -- ...
        nat (LogStr str next ) = tell str >> pure next

However it’s easy to see that we can just as easily use IO instead, so that the entire logic of our program is independent of the way it accesses the outside world, i.e. the edge case. In this way free monads allow us to write pure programs that can be run in a manner as to avoid or create side affects according to what is needed.

However, it’s worth noting that the free monad is no different than any other free construction, it allows a functor to act as a Monad and uses the underlying interpretation of the functor to interpret a monadic computation.gg