Optimising free monad programs using Plated

Posted on October 26, 2017

This document is a Literate Haskell file, available here


In this article I demonstrate how to use classy prisms and Plated to write and apply optimisations to programs written in a free monad DSL.

Plated is a class in lens that provides powerful tools to work with self-recursive data structures. One such tool is recursive bottom-up rewriting, which repeatedly applies a transformation everywhere in a Plated structure until it can no longer be applied.

The free monad has an instance of Plated:

so if you derive Foldable and Traversable for the underlying functor, you can use the Plated combinators on your free monad DSL.

Defining classy prisms for the base functor provides pattern matching on free monad programs for free. When coupled with rewrite, we get a system for applying optimisations to our free monad programs with minimal effort.


Let’s get into it.

 

First, define the DSL. This is a bit of a contrived one:

  • one - “do something once”
  • many n - “do something n times”
  • pause - “take a break”

In this DSL, we are going impose the property that many n should be equivalent to replicateM_ n one.

 

Next, generate classy prisms for the functor.

makeClassyPrisms ''InstF generates the following prisms:

 

Lift the classy prisms into the free monad:

We can now use the prisms as if they had these types:

If one of these prisms match, it means the program begins with that particular instruction, and the Inst a returned is the tail of the program.

 

Now it’s time to write optimisations over the free monad structure. A rewrite rule has the type a -> Maybe a- if the function returns a Just, the input will be replaced with the contents of the Just. If it returns Nothing then no rewriting will occur.

Rule 1: one followed by one is equivalent to many 2

Rule 2: one followed by many n is equivalent to many (n+1)

Rule 3: many n followed by one is equivalent to many (n+1)

 

The last step is to write a function that applies all the optimisations to a program.

getFirst . foldMap (First .) has type [a -> Maybe a] -> a -> Maybe a. It combines all the rewrite rules into a single rule that picks the first rule to succeed for the input.

 

Now we can optimise a program:

The ones before the pause should collapse into many 3, and the instructions after the pause should collapse into many 6.

ghci> optimise program == (many 3 *> pause *> many 6)
True

:)

> Isaac Elliott

Isaac really likes types