Catamorphisms for recursive types

This post should have been written a year and a half ago, when the experimentation it describes arrived at the results you’ll read about. Unlike wine, this extra aging period does not seem to have benefited it in any way. However, I’ll try to remember the excitement I felt reading Brian’s series of posts on catamorphisms in F# and transfer some of it to you, dear reader, in the hope that you’ll rush, read all eight posts of the series in sequence, and then come back and read this one. Because, one thing that I won’t do, is try to explain what is very eloquently explained by Brian in all of eight posts and summarized with this definition:

A catamorphism is a generalization of a fold on lists to an arbitrary data type.

Ok, maybe I’ll expand on this a little. A catamorphism is like a fold in that it encapsulates an operation on a type by allowing you to specify different operations on different “parts” or “cases” of a type, and taking care of “traversing” this type and applying the appropriate operations. But you really must read the whole series by Brian to get a grip on catamorphisms and then understand what I tried to build upon.

In all material I read about catamorphisms, there was always a hint that the approach used to generate catamorphisms for simple or simply recursive types can be extended to mutually recursive types. But I couldn’t find any concrete advice on how to do that and I tasked myself with creating some myself.

I am using essentially the same example types as Brian.

// types capable of representing a small integer expression language
type Op = 
    | Plus 
    | Minus 
type Expr = 
    | Literal of int 
    | BinaryOp of Expr * Op * Expr     // left, op, right
    | IfThenElse of Expr * Expr * Expr // cond, then, else; 0=false in cond
    | Print of Expr                    // prints, then returns that value
    | Newline                          // prints newline

The difference is that the catamorphism will traverse Op as well as Expr, which will make the construction process go recursive all the way.

In order to avoid lots of free-standing functions (signatures will get very convoluted), I’m going to group functions per type, inside “visitor” structs.

type OpVisitor<'resOp> = {

    visitPlus: Op->'resOp
    visitMinus: Op->'resOp

type ExprVisitor<'resOp,'resExpr> = {

    visitLiteral: int->Expr-&gt;'resExpr
    visitBinaryOp: 'resExpr-&gt;'resOp-&gt;'resExpr-&gt;Expr-&gt;'resExpr
    visitIfThenElse: 'resExpr-&gt;'resExpr-&gt;'resExpr-&gt;Expr-&gt;'resExpr
    visitPrint: 'resExpr-&gt;Expr-&gt;'resExpr
    visitNewline: Expr-&gt;'resExpr

The generic arguments are the return types of the visitors. For example, the identity visitor for Expr will be the following, where the generic arguments will be Op and Expr themselves.

let identityExprVisitor = {
    new ExprVisitor<_,_>
    with visitLiteral = (fun _ x -> x)
    and visitBinaryOp = (fun _ _ _ x -> x)
    and visitIfThenElse = (fun _ _ _ x -> x)
    and visitPrint = (fun _ x -> x)
    and visitNewline = (fun x -> x)

The catamorphism for those two types (using the K continuation builder from Brian’s posts) consists of the following two recursive functions.

let rec KFoldOp (vOp:OpVisitor<_>) o = 
    K {
    match o with
    | Plus -> return! vOp.visitPlus  o
    | Minus -> return! vOp.visitMinus  o
and KFoldExpr (vOp:OpVisitor<_>) (vExpr:ExprVisitor<_,_>) o = 
    K {
    match o with
    | Literal(x0) -> return! vExpr.visitLiteral  x0 o
    | BinaryOp(x0,x1,x2) -> return! vExpr.visitBinaryOp (KFoldExpr vOp vExpr x0) (KFoldOp vOp x1) (KFoldExpr vOp vExpr x2) o
    | IfThenElse(x0,x1,x2) -> return! vExpr.visitIfThenElse (KFoldExpr vOp vExpr x0) (KFoldExpr vOp vExpr x1) (KFoldExpr vOp vExpr x2) o
    | Print(x0) -> return! vExpr.visitPrint (KFoldExpr vOp vExpr x0) o
    | Newline -> return! vExpr.visitNewline  o

This approach can be used on any set of mutually recursive types and, if the example above seems too dry and almost mechanical, it is because it has been mechanically produced! Based on the parser in Brian’s FSharpDepthColorizer, I have created a “catamorphism compiler” that parses an F# file and creates catamorphisms for the union types it finds in it. The code is contained in a VS2010 solution which you can download. Project “Catacomp” is the actual compiler.

Have fun with it, and keep on using F#, the only truly interesting mainstream programming language out there.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s