Chapter 5 · Sum types, unions, and `match`

If you come from an imperative language, this is the chapter where you change how you model data. Sum types and the match that goes with them replace half of the class hierarchies, flag-based enums, instanceof chains and visitor patterns you’ve probably been writing. Once you have them in hand, you don’t want to give them up.

The chapter goes from less to more. You start with basic sum types, move through type recursion, work through every form of match, reach unions of existing types — an idea uncommon in mainstream languages — and finish with an arithmetic expression evaluator with typed errors.

5.1 Sum types with `|`

A sum type declares that a value can be one of several distinct constructors. The syntax is direct:

type Color = Red | Green | Blue

Color is a type. Red, Green, Blue are its three constructors. A value of type Color is exactly one of the three. There is no fourth hidden value, no null, no “unknown color”: the type enumerates its inhabitants and stops there.

If you come from a language with enum, this looks similar — with two differences: constructors can carry data, and the compiler verifies that you cover them all when you decide based on the constructor.

Start with the first. A constructor can take positional parameters, like a record with numbered fields:

type Shape
  = Circle(Real)
  | Rectangle(Real, Real)
  | Triangle(Real, Real, Real)

Circle(2.0) is a Shape value with a real inside; Rectangle(3.0, 4.0) carries two, and Triangle(3.0, 4.0, 5.0) three. All three are Shape, but the compiler knows which is which and makes you handle them separately when you consume them.

fn area(s: Shape) : Real =
  match s {
    Circle(r)         -> 3.14159 * r * r
    Rectangle(w, h)   -> w * h
    Triangle(a, b, c) -> {
      let s = (a + b + c) / 2.0          # Heron
      real_sqrt(s * (s - a) * (s - b) * (s - c))
    }
  }

match is an expression that decides based on the constructor. Each arm is a pattern followed by -> and the expression that arm produces. The patterns unpack the data at the same time: in Circle(r), r is the variable bound to the Real that came inside the constructor. There is no separate cast or indexed access; the pattern does the work. The triangle arm applies Heron’s formula with real_sqrt, the square root that comes built in, no import needed.

Three details you’ll use all the time:

The compiler checks exhaustiveness. If you remove the Triangle(...) arm and the compiler knows s : Shape can be a triangle, it doesn’t compile. This saves you from subtle bugs when you add a new constructor: every match that doesn’t cover it becomes a compile error pointing exactly at the spot needing attention.
Constructors are names like any other. When you declare type Color = Red | Green | Blue, kaikai creates four symbols: Color is the type, and Red, Green, Blue are simultaneously types (each with one inhabitant) and values. In chapter 9 you’ll see how this lets you extend a sum type with protocols defined for individual constructors.
The | operator always means union of types. You’ll use it in depth in §5.5: Color = Red | Green | Blue, EvalError = ArithError | EnvError, and Result = Ok(Int) | Err(String) are the same construction. The difference between “declaring new types” and “composing existing types” is decided by the compiler inspecting whether the names on the right are already declared.

The single-member case

There is a corner here that bites early. With two or more members there is no ambiguity, but with just one, type State = Active is an alias: you are giving another name to a type called Active, not declaring a constructor. It is the same shape you write type Meters = Int with, and the compiler cannot guess which one you meant.

A leading bar breaks the tie:

type Evidence = | SameBytecode     # one member: a sum, the ctor exists
type Color = Red | Green           # two or more: no leading bar
type Meters = Int                  # no bar, one name: an alias

Get it wrong and the error says so:

error: unknown type `Active`
  --> x.kai:1:14
    |
  1 | type State = Active
    |              ^
  = help: to declare a one-member sum, write `type State = | Active`

A constructor with no payload never takes parentheses: write Active, not Active().

5.2 Constructors with and without payload

A constructor can:

Carry no data (Red, Green, Blue). It is a unique value of the type, with no parameters.
Carry one or more positional values (Circle(Real), Rectangle(Real, Real)). The constructor is applied like a function to the data to produce the value.

The grammar puts no limit on how many values a constructor carries, but past three or four positional values it pays to declare a record and put it in the payload. The difference between

type Event
  = Login(String, String, Int, Bool)
  | Logout(String, Int)

and

type LoginData = { user: String, ip: String, timestamp: Int, success: Bool }
type LogoutData = { user: String, timestamp: Int }
type Event = Login(LoginData) | Logout(LogoutData)

is that the second reads better wherever you build or destructure an event. The practical rule: if the data names itself by position — a point is (Real, Real) — keep it positional. If the data forces the reader to remember the order, use a record.

Both flavors of constructor in one program: three cases with no payload and three that carry data.

# examples/ch05/01_basic_sums.kai
type Color = Red | Green | Blue

type Shape
  = Circle(Real)
  | Rectangle(Real, Real)
  | Triangle(Real, Real, Real)

fn area(s: Shape) : Real =
  match s {
    Circle(r) -> 3.14159 * r * r
    Rectangle(w, h) -> w * h
    Triangle(a, b, c) -> {
      # Heron's formula, with s as the semi-perimeter.
      let s = (a + b + c) / 2.0
      real_sqrt(s * (s - a) * (s - b) * (s - c))
    }
  }

fn name(c: Color) : String =
  match c {
    Red -> "red"
    Green -> "green"
    Blue -> "blue"
  }

fn main() {
  println("color: #{name(Red)}, #{name(Green)}, #{name(Blue)}")
  let c = Circle(2.0)
  let r = Rectangle(3.0, 4.0)
  let t = Triangle(3.0, 4.0, 5.0)
  println("circle: area = #{area(c)}")
  println("rectangle: area = #{area(r)}")
  println("triangle: area = #{area(t)}")
}

$ kai run examples/ch05/01_basic_sums.kai
color: red, green, blue
circle: area = 12.56636
rectangle: area = 12
triangle: area = 6

5.3 Recursion in types

Now the construction earns its keep: a constructor of a sum type can mention the type itself in its fields. That gives you trees, lists, small graphs, and the representation of any nested structure.

A binary tree:

type Tree
  = Leaf
  | Node(Int, Tree, Tree)

Tree is Leaf (no data) or Node with an integer and two subtrees. The subtrees are Tree themselves, so they can recursively be Leaf or Node, to whatever depth you want.

A function over a tree is also recursive: the base case is Leaf, the recursive case descends into the children.

fn height(t: Tree) : Int {
  case Leaf            -> 0
  case Node(_, l, r)   -> 1 + max_int(height(l), height(r))
}

The pattern Node(_, l, r) ignores the node’s data (height doesn’t need it) and binds the two subtrees to l and r; the function recurses on each and adds one to the max.

The same applies to an arithmetic expression AST:

type Expr
  = Lit(Int)
  | Add(Expr, Expr)
  | Mul(Expr, Expr)
  | Neg(Expr)

fn eval(e: Expr) : Int =
  match e {
    Lit(n)    -> n
    Add(a, b) -> eval(a) + eval(b)
    Mul(a, b) -> eval(a) * eval(b)
    Neg(x)    -> -eval(x)
  }

Building an expression is transparent: Mul(Neg(Add(Lit(2), Lit(3))), Lit(4)) is the literal representation of `-(2 + 3)

4, which evaluates to -20`. The tree and the code that walks it write themselves once you know how to look at it this way.

This replaces the class hierarchies with visitor patterns of object-oriented languages. The key difference: in kaikai, adding a new node to Expr is one line, and every match over Expr in the codebase becomes a compile error pointing at the spots that need attention. In a visitor pattern, you add a new method in each subclass and the compiler does not help you avoid forgetting any.

A tree and an arithmetic expression, each with its recursive function:

# examples/ch05/02_recursive.kai
type Tree
  = Leaf
  | Node(Int, Tree, Tree)

fn height(t: Tree) : Int {
  case Leaf -> 0
  case Node(_, l, r) -> 1 + max_int(height(l), height(r))
}

fn max_int(a: Int, b: Int) : Int =
  if a > b { a } else { b }

# Arithmetic expression AST
type Expr
  = Lit(Int)
  | Add(Expr, Expr)
  | Mul(Expr, Expr)
  | Neg(Expr)

fn eval(e: Expr) : Int =
  match e {
    Lit(n) -> n
    Add(a, b) -> eval(a) + eval(b)
    Mul(a, b) -> eval(a) * eval(b)
    Neg(x) -> -eval(x)
  }

fn main() {
  # Tree:    1
  #         / \
  #        2   3
  #       /
  #      4
  let t = Node(1, Node(2, Node(4, Leaf, Leaf), Leaf), Node(3, Leaf, Leaf))
  println("height = #{height(t)}")

  # Expression: -(2 + 3) * 4
  let e = Mul(Neg(Add(Lit(2), Lit(3))), Lit(4))
  println("eval = #{eval(e)}")
}

$ kai run examples/ch05/02_recursive.kai
height = 3
eval = -20

5.4 `match`: patterns, guards, exhaustiveness

You’ve already used match. Here’s the full picture.

A match takes a scrutinee expression (what’s being inspected) and a series of arms, each with a pattern followed by -> and the expression that arm produces. The arm whose pattern matches the value of the scrutinee is the one that runs; its value is the value of the match.

Patterns kaikai accepts:

Literals: 0, "hi", true. Match the exact value.
Constructors: Some(x), Lit(n), Add(a, b). Match the constructor and bind the data to variables.
Records: Point { x, y }, Point { x: 0, y: _ }.
Lists: [], [h, ...t], [only], [first, second, ...].
Wildcard: _. Matches anything, binds nothing.
Variable: any undeclared identifier. Matches anything and binds the value to that variable.
Constants: MAX, net.MAX. Match values equal to the constant. A qualifier picks a particular module’s.

Patterns nest: Some(Point { x, y }) matches a Some that contains a Point, unpacking x and y in one pass.

Binding or comparing: the identifier rule

The last two entries in that list are the same syntax doing opposite things:

# examples/ch05/06_constant_patterns.kai
const HTTP_PORT: Int = 80
const HTTPS_PORT: Int = 443

fn scheme(p: Int) : String =
  match p {
    HTTP_PORT  -> "http"
    HTTPS_PORT -> "https"
    _          -> "unknown"
  }

HTTP_PORT here is not a variable that swallows any port and binds it. It’s an equality test against 80. The rule is: an identifier in a pattern binds, unless it names a constant in scope — then it compares. Not a matter of capitalization; a lowercase constant compares just the same.

Which means introducing a constant can change what an existing pattern means. If you write a limit -> ... arm meaning to bind, and someone later declares const limit, that arm quietly turns into a comparison.

The compiler has your back on the more common direction of that mistake. A bare binding matches everything, so any arm after it is dead, and it says so:

error: unreachable match arm: previous arm matched every value
  --> x.kai:4:5
    |
  4 |     _      -> "unreachable"
    |     ^
  = note: an earlier unguarded `_` or bare binding already covers this case
  = help: remove this arm, or move it before the catch-all

If you meant to compare and the constant wasn’t in scope, this is the error you’ll get, and it points at the right place.

Guards

A pattern can be followed by if and a condition — a guard — that’s evaluated after the structural match. If the guard is false, the arm doesn’t apply and the next arm is tried:

fn sign(n: Int) : String =
  match n {
    0           -> "zero"
    k if k > 0  -> "positive"
    _           -> "negative"
  }

The pattern k if k > 0 matches any integer, binds it to k, then evaluates k > 0. If true, runs the arm; otherwise moves on. The final _ arm has no guard and matches everything else — integers that are neither zero nor positive.

Guards are convenient but don’t participate in the exhaustiveness check: the compiler can’t know that k > 0 and k < 0 complement each other, so it needs a final guardless pattern that covers “everything else”. If you omit it, it doesn’t compile.

Exhaustiveness

The compiler verifies that every possible inhabitant of the scrutinee’s type is covered. If your Expr has four constructors and your match covers three, it doesn’t compile, and the message doesn’t stop at “something missing”: it tells you what’s missing, what’s covered, and how to fix it:

error: non-exhaustive match on Expr: missing Neg
  --> eval.kai:12:3
    |
 12 |   match e {
    |   ^
  = note: missing variant: `Neg`
  = note: covered: Mul, Add, Lit
  = help: add an arm `Neg -> ...` or a wildcard `_ -> ...`

The wildcard _ covers everything not covered by the preceding arms, so a match with a final _ is trivially exhaustive. But using _ instead of enumerating the cases silences the compiler: when you add a constructor to Expr, the matches with a final _ absorb it without complaint, and you lose the warning.

Practical rule: use _ only when you really don’t care about distinguishing the rest. If there are three cases and all three matter, write the three.

Constant pattern, guard and wildcard in the same match:

# examples/ch05/03_match_guards.kai
fn sign(n: Int) : String =
  match n {
    0 -> "zero"
    k if k > 0 -> "positive"
    _ -> "negative"
  }

# Guards with bindings and patterns
type Point = { x: Int, y: Int }

fn quadrant(p: Point) : String {
  let Point { x, y } = p
  if x == 0 and y == 0 {
    "origin"
  } else if x > 0 and y > 0 {
    "I"
  } else if x < 0 and y > 0 {
    "II"
  } else if x < 0 and y < 0 {
    "III"
  } else if x > 0 and y < 0 {
    "IV"
  } else {
    "on an axis"
  }
}

fn main() {
  println("sign(-5) = #{sign(-5)}")
  println("sign(0)  = #{sign(0)}")
  println("sign(7)  = #{sign(7)}")
  println("quadrant(3,4)   = #{quadrant(Point{x: 3, y: 4})}")
  println("quadrant(-1,-1) = #{quadrant(Point{x: -1, y: -1})}")
  println("quadrant(0,0)   = #{quadrant(Point{x: 0, y: 0})}")
}

$ kai run examples/ch05/03_match_guards.kai
sign(-5) = negative
sign(0)  = zero
sign(7)  = positive
quadrant(3,4)   = I
quadrant(-1,-1) = III
quadrant(0,0)   = origin

5.5 Unions of existing types

So far every | you’ve written had new names on the right — Red, Green, Lit, Circle — that kaikai auto-declares as constructors. But the operator doesn’t require new names. If the names on the right are already declared as types, kaikai builds a union that can carry any value of those types.

This is the key tool for composing errors across layers:

type IdentityError = AccountNotFound | KycExpired | Frozen
type AuthError     = InsufficientBalance | OverDailyLimit

type QueryError = IdentityError | AuthError

QueryError is the union of the two prior types. A value of QueryError is any value of IdentityError or any value of AuthError. There is no new wrapper: AccountNotFound was already a valid value, and now it is also a valid value of QueryError.

That step is called implicit upcast: a variable typed IdentityError fits where QueryError is expected, no conversion:

let id_err: IdentityError = AccountNotFound
let qe: QueryError        = id_err     # OK, no ceremony

Other languages make you do this with wrapper constructors (QEIdentity(IdentityError)), From impls, or manual conversions with map_err. In kaikai, none of those three things exist: the compiler knows IdentityError is a component of QueryError and rewrites the upcast for you.

Pattern matching over unions

A match over a union value has two flavors that kaikai lets you mix freely.

The first, already familiar, enumerates every constructor individually:

fn describe(e: QueryError) : String =
  match e {
    AccountNotFound      -> "id: account not found"
    KycExpired           -> "id: KYC expired"
    Frozen               -> "id: frozen"
    InsufficientBalance  -> "auth: insufficient balance"
    OverDailyLimit       -> "auth: over daily limit"
  }

This works, but is tedious for big unions. And worse, if a component grows — you add RegulatoryHold to AuthError — the match becomes a compile error in five places instead of one.

The second flavor is the narrowing pattern bind : ComponentType, which matches when the value belongs to the named component and binds it under that narrower type:

fn describe(e: QueryError) : String =
  match e {
    ie : IdentityError -> "id: " ++ id_str(ie)
    ae : AuthError     -> "auth: " ++ auth_str(ae)
  }

Each arm delegates to a function that knows that specific component. If AuthError grows, only auth_str changes. The match over QueryError doesn’t notice.

The two forms also mix in a single match when you want to extract a specific case and delegate the rest:

match e {
  AccountNotFound     -> "id: specifically, account missing"
  ie : IdentityError  -> "id: " ++ id_str(ie)        # KycExpired, Frozen
  ae : AuthError      -> "auth: " ++ auth_str(ae)
}

The compiler treats narrowing arms as if they covered every constructor of their component, so exhaustiveness closes correctly.

A deliberate limitation: upcast doesn’t chain

The implicit upcast works only one step:

type IdentityError = AccountNotFound | KycExpired
type AuthError     = OverLimit | DailyCap
type QueryError    = IdentityError | AuthError
type RoutingError  = NotFound | ServerDown
type AppError      = QueryError | RoutingError

fn handle_app(e: AppError) : String = "..."

And a value of the innermost type:

let id: IdentityError = AccountNotFound
handle_app(id)       # ERROR: IdentityError is not a direct
                     # component of AppError.

Although every IdentityError is logically an AppError (through QueryError), the compiler doesn’t search that chain. To go from IdentityError to AppError you must write the intermediate step explicit:

let q: QueryError = id           # one step: IdentityError → QueryError
handle_app(q)                      # another step: QueryError → AppError

I left it that way on purpose. Chained subtyping makes type inference brittle and error messages hard to phrase. The “one step” rule keeps kaikai with a predictable type system whose messages point to the right place.

Two error families declared separately, joined in one signature, and the match that tells them apart:

# examples/ch05/04_unions.kai
type IdentityError = AccountNotFound | KycExpired | Frozen

type AuthError = InsufficientBalance | OverDailyLimit

# Union of two already-declared types.
type QueryError = IdentityError | AuthError

fn id_str(e: IdentityError) : String =
  match e {
    AccountNotFound -> "account not found"
    KycExpired -> "KYC expired"
    Frozen -> "frozen account"
  }

fn auth_str(e: AuthError) : String =
  match e {
    InsufficientBalance -> "insufficient balance"
    OverDailyLimit -> "over daily limit"
  }

# Match with narrowing: each component delegates to its handler.
fn describe(e: QueryError) : String =
  match e {
    ie : IdentityError -> "id: " ++ id_str(ie)
    ae : AuthError -> "auth: " ++ auth_str(ae)
  }

fn main() {
  # Implicit upcast: IdentityError <: QueryError
  let e1: QueryError = AccountNotFound
  let e2: QueryError = OverDailyLimit

  println(describe(e1))
  println(describe(e2))
}

$ kai run examples/ch05/04_unions.kai
id: account not found
auth: over daily limit

5.6 Errors as unions, no wrappers

Errors are where unions pay off most. When a function can fail in several ways that break down into clear categories, the natural pattern is:

Each category is a small sum type.
The composite error is the union of the categories.
Each function returns Result[T, CompositeError].
The ! operator propagates the error of any layer up to the composite Result, via the implicit upcast.

fn check_identity(req: Req) : Result[Account, IdentityError] = ...
fn check_auth(c: Account) : Result[Approved, AuthError] = ...

fn query_balance(req: Req) : Result[Balance, QueryError] {
  let acc = check_identity(req)!     # IdentityError <: QueryError
  let app = check_auth(acc)!         # AuthError <: QueryError
  Ok(load_balance(app))
}

Each ! unpacks the Ok and propagates the Err with the correct upcast to the outer Result[_, QueryError]. Zero wrappers, zero map_err, zero From. The signature of query_balance documents exactly which errors it can emit, and the compiler ensures every one of them is covered when something consumes the result.

What `!` does internally

! is a return in disguise. The line

let acc = check_identity(req)!

is exactly equivalent to:

let acc = match check_identity(req) {
  Ok(x)  -> x                  # unpack and continue
  Err(e) -> return Err(e)      # exit query_balance with that error
}

For Option[A] the desugar is analogous: Some(x) unpacks, None triggers return None.

Three things to pin down:

It’s not a panic or an exception. The program does not abort; the current function ends normally returning the Err or None to its caller. Control flows out one level only, no further.
It only works if the current function returns a compatible type. If your function returns Int, you can’t use ! on a Result inside — the return Err(e) has nowhere to land. The compiler tells you so clearly.
The upcast happens at the return. When check_identity(req) returns Result[_, IdentityError] but query_balance declares Result[_, QueryError], the return Err(e) applies the upcast IdentityError <: QueryError on the way out. That’s why ! and union errors compose so well: each level of the cascade absorbs the error of the layer below without writing conversions.

If you come from Rust, this is exactly the ? operator. If you come from Swift, it’s what try with throws does. If you come from Haskell, it’s the do-notation over Either collapsed into a single symbol.

Compare it with the typical imperative version:

# Python: nothing in the return type tells you what may fail
def query_balance(req):
    acc = check_identity(req)   # may throw AccountNotFound, KycExpired...
    app = check_auth(acc)       # may throw InsufficientBalance...
    return load_balance(app)

The caller of query_balance in Python has to read the inner functions’ code — or the docs, if any — to know which exceptions to expect. In kaikai the signature tells them.

5.7 Case study: evaluator with typed errors

We close the chapter with an integrative case. You’ll build an evaluator of arithmetic expressions with two categories of error:

Arithmetic: division by zero, square root of a negative.
Environment: undefined variable.

The two form a union, EvalError, and the evaluator returns Result[Real, EvalError]. Full code in examples/ch05/05_evaluator.kai; here you walk through the interesting parts.

The AST

type Expr
  = Lit(Real)
  | Var(String)
  | Add(Expr, Expr)
  | Mul(Expr, Expr)
  | Div(Expr, Expr)
  | Sqrt(Expr)

Six constructors, four of them recursive. Var(String) introduces something new compared to the chapter 1 evaluator: expressions can now reference variables, so the evaluator needs an environment that associates names with values.

The errors

type ArithError = DivByZero | NegativeSqrt(Real)
type EnvError   = Undefined(String)
type EvalError  = ArithError | EnvError

Three types: two categories and the union. Three constructors in total, distributed over categories that make sense on their own. NegativeSqrt(Real) carries the value that was passed to sqrt, useful for the final error message. Undefined(String) carries the name of the missing variable.

The environment

type Env = [(String, Real)]

fn lookup(env: Env, name: String) : Result[Real, EvalError] {
  case [], _                          -> Err(Undefined(name))
  case [(k, v), ...], n when k == n   -> Ok(v)
  case [_, ...rest], n                -> lookup(rest, n)
}

Env is an alias for a list of pairs — linear lookup, enough for a toy evaluator. lookup is written in the multi-clause form of chapter 6: each case lists one pattern per argument separated by comma, with an optional when for guards. Three cases:

Empty list: variable wasn’t there; return an error.
Head with the key being looked up: success.
Any other head: continue with the tail.

Notice the Err is of type EvalError, not EnvError — but Undefined(name) constructs as EnvError and the implicit upcast promotes it to EvalError at the return site, no explicit conversion.

eval, next, uses the match e { ... } form, which reads better when you dispatch on a single argument of a sum type with many constructors. The two forms coexist in the same file without tension.

The evaluator

fn eval(env: Env, e: Expr) : Result[Real, EvalError] =
  match e {
    Lit(n)    -> Ok(n)
    Var(name) -> lookup(env, name)
    Add(a, b) -> {
      let va = eval(env, a)!
      let vb = eval(env, b)!
      Ok(va + vb)
    }
    Mul(a, b) -> {
      let va = eval(env, a)!
      let vb = eval(env, b)!
      Ok(va * vb)
    }
    Div(a, b) -> {
      let va = eval(env, a)!
      let vb = eval(env, b)!
      if vb == 0.0 { Err(DivByZero) } else { Ok(va / vb) }
    }
    Sqrt(x) -> {
      let v = eval(env, x)!
      if v < 0.0 { Err(NegativeSqrt(v)) } else { Ok(real_sqrt(v)) }
    }
  }

Each match case corresponds to a constructor of Expr. Recursive cases use ! to evaluate subtrees and propagate any error that appears; cases that can fail locally (division by zero, negative sqrt) construct an Err of the appropriate type and let the upcast promote it.

The ! appears several times; read it carefully. eval(env, a)! means: if eval(env, a) returns Ok(v), bind va to v; if it returns Err(e), exit immediately from the current function returning that Err.

Printing the result

fn describe(e: EvalError) : String =
  match e {
    DivByZero        -> "division by zero"
    NegativeSqrt(v)  -> "sqrt of negative (#{v})"
    Undefined(name)  -> "undefined variable: " ++ name
  }

fn print_result(r: Result[Real, EvalError]) : Unit =
  match r {
    Ok(v)  -> println("ok: #{v}")
    Err(e) -> println("error: " ++ describe(e))
  }

describe consumes an EvalError enumerating its three constructors. The match enumerates because each constructor gets its own message; if the logic differed per category, narrowing would fit better.

The main program assembles the environment, evaluates several expressions, and prints them:

fn main() {
  let env: Env = [("x", 9.0), ("y", 4.0)]

  print_result(eval(env, Add(Var("x"), Var("y"))))  # ok: 13
  print_result(eval(env, Sqrt(Var("x"))))            # ok: 3
  print_result(eval(env, Div(Lit(10.0), Lit(0.0))))  # error: division by zero
  print_result(eval(env, Sqrt(Lit(-1.0))))           # error: sqrt of negative (-1)
  print_result(eval(env, Var("z")))                  # error: undefined variable: z
}

The pretty thing about this case: every error is documented in the type of the evaluator. If later you want to add an TypeError (say, attempting to add two non-numbers), you declare the new category, include it in EvalError, and the compiler walks you to every place that needs to adapt.

Exercises

5.1. Define type Maybe[a] = Just(a) | Nothing (another form of Option) and write fn or_else[a](m: Maybe[a], default: a) : a returning the value if Just, the default if Nothing. Note: Nothing is also a kaikai primitive type (the bottom type from chapter 3); use Empty or another name if shadowing bothers you.

5.2. Extend the §5.7 evaluator to support subtraction: add Sub(Expr, Expr) to the AST, add the matching arm in eval, and verify that 2 - 3 evaluates to -1. How many lines did you have to change? How many places did the compiler walk you to?

5.3. Define a binary decision tree:

type Decision[a]
  = Leaf(a)
  | Question(String, Decision[a], Decision[a])

where a Question has text, a “yes” branch and a “no” branch. Write fn apply[a](d: Decision[a], answers: [(String, Bool)]) : Option[a] walking the tree following the answer to each question, returning Some with the final decision if it reaches a Leaf, or None if some question has no answer.

5.4. Take the union example with IdentityError and AuthError. Add a third component RoutingError with two constructors. Rewrite the match with narrowing so the code stays equally short. Then add a new constructor to AuthError (say Blocked) — what happens to your code? How many places does the compiler intervene?

5.5. Create a sum type for a chat message: type Message = Text(String) | Image(String, Int, Int) | Audio(String, Int) (path, dimensions or duration). Write a function fn description(m: Message) : String returning a human description, and a function fn heavy(m: Message) : Bool returning true if the message is image or audio. The second function should use narrowing in the match, not enumeration.

5.6. On paper, draw the evaluation tree the §5.7 evaluator builds when processing the expression Mul(Add(Var("x"), Lit(2.0)), Var("y")) with environment [("x", 9.0), ("y", 4.0)]. How many calls to eval? How many to lookup? In what order? This helps you understand why the ! operator cuts execution as soon as something fails: three cascaded calls, one line per level.

5.1 Sum types with |