Algebraic data types and recursive models

The idea

A data declaration can describe alternatives with different required fields. Each constructor identifies a variant, while its arguments hold the data that variant needs. This makes the representation more precise than a record filled with unrelated optional values or string tags. A function consuming the type should handle every constructor that belongs to its contract.

Recursive algebraic types model trees and syntax naturally. The recursive function follows the type’s structure: a leaf supplies a base result and a compound node combines results from its children. Keep the meaning of each constructor visible in the corresponding equation. Adding a new constructor should prompt a review of all consumers, using compiler warnings for incomplete patterns as a maintenance aid.

data Expr = Lit Integer | Add Expr Expr | Mul Expr Expr
evaluate :: Expr -> Integer
evaluate (Lit n) = n
evaluate (Add a b) = evaluate a + evaluate b
evaluate (Mul a b) = evaluate a * evaluate b
main = print (evaluate (Add (Lit 2) (Mul (Lit 3) (Lit 4))))

14

The expression tree encodes multiplication as a child of addition, so the recursive evaluator produces two plus twelve.