Previously, we have demonstrated what is a recursion schemes and how to define recursive data type(such as AST) using it. We have shown that some built-in traversal mechanisms are easily defined using such a style(such as foldFix).

Today, we are going to view the whole concept in another way: how recursion schemes is valuable in incremental development.

the need for incremental development

Suppose we are on a language project, and initially, we have defined an Functor based on basic lambda calculus:

data Prim
  = PInt Int
  | PFloat Float
  | PBool Bool
  | PStr String
  | Unit
  deriving (Show, Eq)

data ExprF r
  = Var String     -- ^ Variables.
  | Prim Prim      -- ^ Primitives.
  | App r r        -- ^ Applications.
  | Lam String r   -- ^ Abstractions.
  | Constr String
  deriving (Functor)

Then we happily apply Fix around ExprF to build an AST:

type Expr = Fix ExprIn

Now comes the pretty function for pretty printing. This time, we use a function definition based on typeclass, soon you will find the very benefit of doing so:

class Pretty a where
  pretty :: a -> String

We firstly define pretty function on the Functor ExprC r:

instance Pretty Prim where
  pretty = show

instance Pretty String where
  pretty = show

instance (Pretty r) => Pretty (ExprC r) where
  pretty (Var v) = pretty v
  pretty (Prim p) = "(" ++ pretty p ++ ")"
  pretty (App e1 e2) 
    = "(App " ++ pretty e1 ++ " " ++ pretty e2 ++ ")"
  pretty (Lam v e) 
    = "fun " ++ pretty v ++ " -> " ++ pretty e
  pretty (Constr sig fv) 
    = "(" ++ pretty fv ++ " : " ++ pretty sig ++ ")"

And then we define pretty function on our AST:

instance Pretty Expr where 
  pretty (Fix x) = pretty x

done? Yes! Done!

What we have obtained, is a way to define a traversal function on AST layer by layer:

• We firstly define the function on the Functor layer

• then define it on the FixPoint layer, and this recursive mechanism is possible thanks to typeclass.

Now comes to the incremental needs: we want to add new nodes on this AST, moreover, we want it to be one layer above the original AST:

data FuncBody = FuncBody ([String], Expr)
data FuncDef = Func (Expr, FuncBody)

That is, we define a FuncDef node which should be composed of Expr, and we still want it naturally fit into our AST!

Take a look at this need, you may immediately recognized that how hard to merge this into our existing code. The fact is that if FuncDef is one layer above the existing AST, it will never type check if we inject such node directly into existing AST.

However, using recursion schemes, this becomes possible!

the solution using recursion schemes

Let's starts with a slight rewrite of the definition above:

newtype FuncBody r = FuncBody ([String], ExprC r)
  deriving (Functor)
newtype FuncDef r = Func (ExprC r, FuncBody r)
  deriving (Functor)

WoW, we just defined another Functor based on some r, and indeed, this r should be the same as r in ExprF r. Now we have two Functor, we just need to merge them into a single one, and build FixPoint around it:

data ExprC r = E (ExprF r)
  | F (FuncDef r)
  deriving (Functor)

type Expr = Fix ExprC

then, what happed to the existing pretty function? we just need to add support on our newly defined nodes, and all existing code based on ExprF r does not need to change:

instance (Pretty r) => Pretty (ExprC r) where 
  pretty (E e) = pretty e 
  pretty (F (Func (h, FuncBody (argTys, body)))) = pretty h

This way, we have achieved a incremental development with almost no change of our code!

discussion

The complexity added by recursion schemes and the less flexiblity of the traversal algorithm it provides are the two reasons why it is not so popular among haskellers(indeed, because of this, some of my colleages don't buy it).

However, the benefit of enabling incremental development is a strong pros for using it in any ongoing project.

There is another benefit of using recursion schemes, which lies in its connection with free monad, we will cover it in the next post.