← All Examples ADTs

Calculator

An expression tree built with recursive algebraic data types. The evaluator walks the tree with pattern matching -- a textbook functional programming pattern.

Source Code

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

fn evaluate(expr: Expr) -> Int {
  match expr {
    Num(n) => n
    Add(a, b) => evaluate(a) + evaluate(b)
    Mul(a, b) => evaluate(a) * evaluate(b)
    Neg(e) => 0 - evaluate(e)
  }
}

fn show_expr(expr: Expr) -> String {
  match expr {
    Num(n) => show(n)
    Add(a, b) => "(" <> show_expr(a) <> " + " <> show_expr(b) <> ")"
    Mul(a, b) => "(" <> show_expr(a) <> " * " <> show_expr(b) <> ")"
    Neg(e) => "(-" <> show_expr(e) <> ")"
  }
}

fn main() {
  let expr = Add(Mul(Num(3), Num(4)), Neg(Num(5)))
  println("Expression: " <> show_expr(expr))
  println("Result: " <> show(evaluate(expr)))
}

What This Demonstrates

• Recursive algebraic types -- Expr variants contain other Expr values, forming a tree structure.
• Destructuring in patterns -- Add(a, b) extracts the two sub-expressions from the variant.
• Interpreter pattern -- evaluate recursively walks the tree, computing a result. show_expr does the same to produce a string representation.
• String concatenation with <> -- Builds formatted output by joining string fragments.

Line-by-Line Breakdown

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

A recursive sum type. Num holds a leaf integer; Add and Mul hold two sub-expressions; Neg holds one.

fn evaluate(expr: Expr) -> Int

A recursive evaluator. Each variant maps to an arithmetic operation on its children's evaluated results.

Neg(e) => 0 - evaluate(e)

Negation implemented as subtraction from zero. JAPL uses standard arithmetic operators.

fn show_expr(expr: Expr) -> String

A pretty-printer that traverses the same tree structure, producing parenthesized infix notation.

let expr = Add(Mul(Num(3), Num(4)), Neg(Num(5)))

Constructs the expression tree (3 * 4) + (-5). Evaluates to 7.

Try Modifying

• Add a Sub(Expr, Expr) variant for subtraction.
• Add a Div(Expr, Expr) variant that returns a Result type to handle division by zero.
• Write a simplify function that reduces expressions like Add(Num(0), e) to just e.
• Add variable bindings: Var(String) and an environment lookup.