I'm excited to announce a new open-source library! It's called 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. 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:

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

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

As promised, the free monoid is itself a monoid.

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:

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

Then its generic representation would be:

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:

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.

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

Now, I can do:

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:

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:

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:

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:

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. 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.

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.

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 and here. 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 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:

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:

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.

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.

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 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 by your's truly and @paluh, there are some other great libraries for working with free monads:

• purescript-run: Federate free monads together into an uber-monad using the Variant pattern.
• 1purescript-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!