Recursive datatypes
While the list type is predefined, we can also define our own recursive algebraic datatypes.
Arithmetic expressions
The Expr datatype is a symbolic representation of arithmetic expressions:
data Expr = Lit Int | Add Expr Expr
The recursive datatype Expr has two constructors:
- The first,
Lit, is the base case; it represents a trivial expression that is just anIntconstant (aka literal) - The second constructor,
Add, is a recursive case; an addition is built out of two smaller expressions (also called subexpressions)
For example, we symbolically represent 2 + 5 as Add (Lit 2) (Lit 5).
Of course, a symbolic expression is just data; it does not compute. To actually evaluate expressions, we need to write an evaluation function:
eval :: Expr -> Int eval (Lit n) = n eval (Add e1 e2) = eval e1 + eval e2
This function has a base case that returns the Int value of the literal and a recursive case for Add...