Functions as data structures

In this last section, we will aim to further shift our perspective away from functions as a mechanism to perform computations on functions as data, or, more specifically, on functions as data structures.

Evaluation with many variables

In Chapter 3, Recursion, we looked at an interpreter for a small expression language that features one variable. Let us generalize this now to expressions that can contain many different variables:

data Expr = Var String | Lit Int | Add Expr Expr

This data type has a constructor, Var, to denote a variable expression. The constructor’s String field identifies which of the possibly many variables is referenced. For example, the expression x + (y + 3) would be written as follows:

expr :: Expr
expr = Add (Var "x") (Add (Var "y") (Lit 3))

When evaluating an expression like this, we need to know what values the "x" and "y" variables take. This was easy in Chapter 3,...