Writing an interpreter using fold

fold is a Swiss Army knife in functional programming. It is expressive enough to write an interpreter for a simple functional programming language.

Let’s start with a simple arithmetic language.

> data Expr = Const Int
>           | Add Expr Expr
>           | Mul Expr Expr

Writing an interpreter for this language is trivial.

> interp :: Expr -> Int
> interp (Const x) = x
> interp (Add e1 e2) = interp e1 + interp e2
> interp (Mul e1 e2) = interp e1 * interp e2

Writing a pretty printer is also easy.

> pretty :: Expr -> String
> pretty (Const x) = show x
> pretty (Add e1 e2) = "(" ++ pretty e1 ++ " + " ++ pretty e2 ++ ")"
> pretty (Mul e1 e2) = "(" ++ pretty e1 ++ " * " ++ pretty e2 ++ ")"

Sensitive readers might have noticed the duplication of code in interp and pretty. Yes, recursion on the structure of Expr is repeated.

We can extract recursion as foldExpr and algorithms as ExprA. foldExpr does recursion on the structure of Expr regardless of the algorithm being used.

> data ExprA a = ExprA
>   { val :: Int -> a
>   , add :: a -> a -> a
>   , mul :: a -> a -> a
>   }
> 
> foldExpr :: ExprA a -> Expr -> a
> foldExpr alg (Const i)   = val alg i
> foldExpr alg (Add e1 e2) = add alg (foldExpr alg e1) (foldExpr alg e2)
> foldExpr alg (Mul e1 e2) = mul alg (foldExpr alg e1) (foldExpr alg e2)

Now it is possible to define the interpreter just by giving val, add and mul functions.

> interpA :: ExprA Int
> interpA = ExprA
>   { val = id
>   , add = (+)
>   , mul = (*)
>   }

The same goes for pretty printer.

> prettyA :: ExprA String
> prettyA = ExprA
>   { val = show
>   , add = \a b -> "(" ++ a ++ " + " ++ b ++ ")"
>   , mul = \a b -> "(" ++ a ++ " * " ++ b ++ ")"
>   }

Here is our interp' function defined in terms of foldExpr and interpA.

> interp' :: Expr -> Int
> interp' = foldExpr interpA

We successfully isolated algorithms from recursion, but we are still not satisfied. ExprA is mostly duplication of Expr and defining foldExpr is boilerplate.

We can fix this by introducing F-algebras and catamorphisms. Interested readers might want to take a look at Bartosz Milewski’s Understanding F-Algebras article.