Freeing Free Monads with Free ADTs
Tags: functional
Published: 2021-02-16 16:13:29

---
title: Freeing Free Monads with Free ADTs
published: true
description: How generics can significantly reduce boilerplate away from working with free monads
tags: functional
cover_image: https://images.unsplash.com/photo-1516081073616-833a87ca7516?ixid=MXwxMjA3fDB8MHxwaG90by1wYWdlfHx8fGVufDB8fHw%3D&ixlib=rb-1.2.1&auto=format&fit=crop&w=800&q=80
---

I'm excited to announce a new open-source library!  It's called [`purescript-freer-free`](https://github.com/meeshkan/purescript-freer-free), and it eliminates ~70% of the boilerplate when working with free monads in PureScript. It's a collaboration between myself and [@paluh](https://github.com/paluh). The article below talks a bit about how the library works and hopefully gives some insights into free constructions and generics.

# Free

> Every claim I make below about category theory is hand-wavey. Not because I don't think you'd understand the non-hand-wavey argument, but because I barely understand this stuff in the first place!

In category theory, "free" constructions abound. A free `X` is an `X` that can be turned into any other `X` via a function. For example, the _Free Monoid_ is the list. A list is itself a monoid because it has a append operation (list concatenation) and an identity element under this operation (the empty list). A list of strings (strings are monoids because they can be concatenated and there is an identity element aka the empty string `""`) can be turned into a string via the following function:

```haskell
fold (<>) ["a","b","c"] -- "abc"
```

Integers are monoids under addition with 0 as the identity. A list of integers can be turned into a sum via the following function

```haskell
fold (+) [1,2,3] -- 6
```

As promised, the free monoid is itself a monoid.

```haskell
fold (<>) [[1],[2],[3]] -- [1,2,3]
```

To understand why other monoids aren't free, ask yourself "What's a "logical" transformation to get from "abc" to 6?"  Pretty hard to drum up one, huh? That's because neither `String` or `Int` is a free monoid. In fact, there is only ever one free construction in a category. In the category of monoids, the free monoid is _THE_ free monoid.

# Free algebraic data types

Free algebraic data types, or ADTs, are called _generics_. A generic is itself an ADT that can be turned into any other ADT in a given language.  Let's see how they work in PureScript!

If I have the ADT `Animal` defined as follows:

```haskell
data Animal a = Dog | Cat String a | Hamster (Boolean -> a)
```

Then its generic representation would be:

```haskell
type GenericAnimal a = Sum (Constructor "Dog" NoArgumenet)
  (Sum (Constructor "Cat"
       (Product (Argument String) (Argument a)))
       (Constructor "Hamster" (Argument (Boolean -> a))))

fluffy = Inr (Inl (Constructor (Product ((Argument "fluffy") (Argument unit))))) :: GenericAnimal Unit
```

I can get from my `GenericAnimal` fluffy to her `Animal` version with a transformation function.  However, if I have another ADT, say `data Silly = Boo`, I can't get back to `Animal`. There aren't enough ways to create a `Silly` to get back an `Animal` or vice versa.

The killer features of generics is that, when dealing with values, we can get _back_ to the original from the generic. This is not true of strings. For example, if I give you `"abc"` and ask how I got there, one person may guess `"a" <> "bc"` and then other `"abc" <> "" <> "" <> ""`. Both are correct. But if you give me a `Cat "fluffy" 42` (ie in a pattern match) and ask me to make a generic value from this, I know the path.

In this way, generics are peculiar free constructions.  Like other free constructions, they are structure-preserving. But unlike other free constructions, their targets (ADTs) _also_ preserve structure at the value-level. So why are generics any "freer" than other ADTs? What makes generics the "free ADT" is that they are _just_ right in Goldilocks-ian fashion.  They have the minimum necessary components to describe _all_ other ADTs. No more, no less.

Fear not, though - generics are not _that_ different than their other free cousins. Generics actually _do_ erase structure, but on the type level. As a reminder, when we do `fold (<>) ["abc","d","ef"]`, we erase structure at the value-level by smooshing everything together.  We can't get back the original elements. Generics do the same thing with types. The monster-type below:

```haskell
Sum (Constructor "Dog" NoArgumenet)
  (Sum (Constructor "Cat"
       (Product (Argument String) (Argument a)))
       (Constructor "Hamster" (Argument (Boolean -> a))))
```

gets translated to a type `Animal a`. Just like when we concatenate strings or sum up numbers, on the type-level, Animal is "smooshed". We have no way to go backwards in type-land to the generic. What makes generics remarkable is that generics have their dual life in the value-land that _does_ allow for this back and forth.

# Using generics to bring typeclasses to ADT constructors

If you can get to any ADT from a generic, it stands to reason that you can do operations on generics rather than doing them on individual ADTs. To do this, though, you need a typeclass that binds generics to their representations.

```haskell
class Generic a rep | a -> rep where
  to :: rep -> a
  from :: a -> rep
```

Now, I can do:

```haskell
instance genericAnimal :: Generic (Animal a) (Sum (Constructor "Dog" NoArgumenet)
  (Sum (Constructor "Cat"
       (Product (Argument String) (Argument a)))
       (Constructor "Hamster" (Argument (Boolean -> a)))))
```

Because that's no fun to write, the team that works on the PureScript compiler provides the ability to derive this type automatically, so you just have to write:

```haskell
derive instance genericAnimal :: Generic (Animal a) _
```
and it will fill in the blank.

Zooming out for a second, typeclasses are just spreadsheets with variables (like `a` and `rep`) as the columns and instances as the rows. Using variables, we can even have an instance of a typeclass that describes many "rows" in one fell swoop. Using this strategy, we can create typeclasses that operate on all generics that share a certain property and then call `to` on them, then we can operate on their representations.

As an example, let's say that we want to take all ADTs of the form `Foo a = Foo a` and get back a `Foo Unit`. Let's call that operation `wham`. We can do:

```haskell
class Wham f where
  wham :: forall name. (Generic (f Unit) (Constructor name (Argument Unit))) => f Unit

instance whamWham :: Wham f where
  wham = to (Constructor (Argument unit))

data Foo a
  = Foo a

derive instance gFoo :: Generic (Foo a) _

fooWham = wham :: Foo Unit
```

So that's a lot of code for something that could have just been:

```haskell
bam :: forall f. (forall a. a -> f a) -> f Unit
bam = (#) unit

fooBam = bam Foo :: Foo Unit
```

But the advantage of the first approach is that we have an indelible, immutable, compiler-enforced relationship defined by the typeclass. That means that every ADT with the same structure belongs to `Wham`.

# From ADT constructors to free monads

The _free monad_ is a monad that can be turned into any other monad via a natural transformation. It follows the same pattern as the free monoid (list) and free ADT (generic) I described above.

Free monads, to be "free", are the minimal-viable-monad. They have no side effects.  But a monad without side effects is like a trip to Finland without seeing Kuopio - what's the point?  Free monads are useful when we want to model a program without specifying how the side effects will be executed, and if we're talking about a program, we're talking about something concrete.  It "does stuff." So really, free monads are not _that_ free in their application: they only make sense in that they are linked to a finite, circumscribed collection of actions, AKA a program.

ADTs are a great way to model the actions that comprise our monadic context. For example, at Meeshkan, we use the following ADT to describe how we fetch assets and upload them to AWS S3:

```haskell
data S3SquirrelProgramF a
  = GetETagForResource String (Maybe String -> a)
  | GetS3InfoFromDBOnCacheHit String (Maybe String) (Maybe S3Info -> a)
  | DownloadResourceToFile String String (Unit -> a)
  | ReadFileToBuffer String (Buffer -> a)
  | GenerateUUID (String -> a)
  | UploadObjectToS3 String String Buffer (Unit -> a)
  | WriteEtagAndS3InfoToDb String (Maybe String) String String (Either Error Unit -> a)
  | FreeLog String (Unit -> a)
  | FreeThrow Error (Unit -> a)
```

Those are the elements of the program, and we mix and match them as we please.  The way we transform those into a free monad is using [`purescript-free`](https://github.com/purescript/purescript-free). In the "bad old days" (meaning a couple days ago, before `purescript-freer-free` was released) we'd use a function from `purescript-free` called `liftF` to turn the ADT above into a monad.

```haskell
getETagForResource :: String -> Free S3SquirrelProgramF String
getETagForResource url = liftF $ GetETagForResource url identity

freeLog :: String -> Free S3SquirrelProgramF Unit
freeLog msg = liftF $ GetETagForResource msg unit

```

we can now write a program that gets our etag and logs it.

```haskell
program = do
  etag <- getETagForResource
  freeLog (show etag)
```

And later we can provide an implementation, for example mocks in a test or a production connection to AWS S3.

There are many great articles on why Free Monads are the bee's knees, notably by Gabriel Gonzalez [here](https://www.haskellforall.com/2012/06/you-could-have-invented-free-monads.html) and [here](https://www.haskellforall.com/2012/07/purify-code-using-free-monads.html).  At the end of this article, I'll give a couple of reasons that I like to use them. But they are also super annoying to work with - you have to write all those functions! And even worse, you have to do it twice! Once to make the free monad, and once to transform it into the execution monad (ie `Aff` or `IO` or `Identity` or whatever).  That's what [`purescript-freer-free`](https://github.com/meeshkan/purescript-freer-free) fixes.

The basic strategy of `purescript-freer-free` is exactly what I showed above. If you know that every element of a free monad's underlying ADT implements `Generic` in a predictable way (ie how the PS compiler does it) _and_ has branches that end with either `a` or `(b -> a)`, you can use generics, like we did with `wham`, to create both the constructors _and_ the interpreter.  In the Meeshkan codebase, that looks like this:

```haskell
data S3SquirrelProgramF a
  = GetETagForResource String (Maybe String -> a)
  | GetS3InfoFromDBOnCacheHit String (Maybe String) (Maybe S3Info -> a)
  | DownloadResourceToFile String String (Unit -> a)
  | ReadFileToBuffer String (Buffer -> a)
  | GenerateUUID (String -> a)
  | UploadObjectToS3 String String Buffer (Unit -> a)
  | WriteEtagAndS3InfoToDb String (Maybe String) String String (Either Error Unit -> a)
  | FreeLog String (Unit -> a)
  | FreeThrow Error (Unit -> a)

derive instance functorS3SquirrelProgramF :: Functor S3SquirrelProgramF

derive instance genericS3SquirrelProgramF :: Generic (S3SquirrelProgramF a) _

type S3SquirrelProgram
  = Free S3SquirrelProgramF

f :: Constructors S3SquirrelProgramF S3SquirrelProgram
f = constructors (liftF :: S3SquirrelProgramF ~> S3SquirrelProgram)
```

The function `constructors` attaches free monads to an extensible record that can be used in a `do` block:

```haskell
program = do
  f.downloadResourceToFile "https://foo.com/a.txt" "a.txt"
  buf <- f.readFileToBuffer "a.txt"
  f.uploadObjectToS3 "bucket" "key" buf
```

and then for the interpreters.

```haskell
s3SquirrelInterpreter :: RDSEnv -> S3SquirrelProgramF ~> Aff
s3SquirrelInterpreter rdsEnv =
  interpreter
    { getETagForResource: getETagForResourceAff
    , getS3InfoFromDBOnCacheHit: getS3InfoFromDBOnCacheHitAff rdsEnv
    , downloadResourceToFile: downloadResourceToFileAff
    , readFileToBuffer: readFileToBufferAff
    , generateUUID: generateUUIDAff
    , freeLog: liftEffect <<< Log.info
    , freeThrow: (throwError :: Error -> Aff Unit)
    , uploadObjectToS3: uploadObjectToS3Aff
    , writeEtagAndS3InfoToDb: writeEtagAndS3InfoToDbAff rdsEnv
    }
```

Where each value in the record is the effectful version of the underlying ADT's constructor.  After refactoring using `purescript-freer-free`, we were able to shave off ~300 lines of code from ~5 free monads, plus avoid annoying mistakes that come from the incorrect passing of destructured arguments in a pattern match to a delegate function.

# Postlude

Most people I know that enjoy writing code in an FP-style don't like working with free monads. This used to be understandable because of the boilerplate, but now y'all have no excuse :-P No, I kid, I kid, there are lots of good reasons not to use free monads. The two I hear most often are.

### Use a reader monad + an effectful context like Effect

Totally works, and often times it's a coin-flip with free monads. The reason I've started avoiding this is because I'll often forget to mock stuff out as I'm building up the effectful monad, then testing becomes too much of a pain, and then I'll forget what's mocked and what's not.  Free monads force you to explicitly declare all side effects, which in addition to helping with mocking has the advantage of being nice documentation for your colleagues.

### Use typeclasses

Also totally works.

```haskell
class Program m where
  doStuff :: String -> m Unit
  doMoreStuff :: String -> m Number

instance affProgram :: Program Aff where
  doStuff = const $ pure unit
  doMoreStuff = const $ pure 42.0
```

This fixes the mocking problem in that all dependencies are explicitly defined in the typeclass. The issue here is that if you want more than one possible implementation in the `Aff` monad, or if you want to mix and match different implementations, it gets tricky. You need to bring in newtypes and class constraints to get it to work out, which makes the code potentially harder to follow.

### Parting shot

I find that free monads allow for better testability and easier swapping of implementations in certain situations. That said, we also have services at Meeshkan that are so tightly coupled to the [`Aff`](https://github.com/purescript-contrib/purescript-aff) monad that making a free monad just takes too much time, so we roll with `Aff` and write a good end-to-end test.

Bottom line - decide for yourself! In addition to the shiny new  [`purescript-freer-free`](https://github.com/meeshkan/purescript-freer-free) by your's truly and [@paluh](https://github.com/paluh), there are some other great libraries for working with free monads:

- [`purescript-run`](https://github.com/natefaubion/purescript-run): Federate free monads together into an uber-monad using the `Variant` pattern.
- [1purescript-freet`](https://github.com/purescript-contrib/purescript-freet): Make your free monad part of a monadic stack.

I hope you enjoy working with `purescript-freer-free`!  We use it at Meeshkan because we take mocking and testing super-seriously so that you can take it slightly-less-seriously.  If you wanna see how, [sign up on https://app.meeshkan.com](https://app.meeshkan.com)!