Tutorial

6. Inductive data types¶

An inductive data type builds finite values from its constructors. An expression, for example, can be a number or an addition of two expressions. Declare recursive fields with the parameter R and store values in Node.

fp.match supports structural recursion over these values. Each clause chooses whether to receive a recursive field as stored or as the result of matching that child. Evaluation uses an explicit stack, so matching a value a million levels deep does not overflow the native stack.

Evaluate, render and simplify an expression¶

expression.mojo Download

"""A recursive expression type: evaluate, render and simplify it with clauses.

Each clause handles one constructor. A field declared with the result type
arrives already evaluated; a field declared as `Expr` arrives as it is. `If`
continues with the branch it takes, so the other branch is never evaluated.
"""
import fp
from fp.adt import Data, Cases, Node, Value
from fp.matching import Next


@fieldwise_init
struct Num(Copyable, Equatable):
    var value: Int


@fieldwise_init
struct Add[R: Value](Movable):
    var left: Self.R
    var right: Self.R


@fieldwise_init
struct Mul[R: Value](Movable):
    var left: Self.R
    var right: Self.R


@fieldwise_init
struct If[C: Value, B: Value](Movable):
    var cond: Self.C
    var then: Self.B
    var other: Self.B


struct Expr(Data):
    comptime Layer[R: Value] = Cases[Num, Add[R], Mul[R], If[R, R]]


comptime E = Node[Expr]


def evaluate(e: E) -> Int:
    return fp.match(e,
        lambda (n: Num) -> Int: n.value,
        lambda (a: Add[Int]) -> Int: a.left + a.right,
        lambda (m: Mul[Int]) -> Int: m.left * m.right,
        lambda (c: If[Int, E]) -> Next[E]: Next(c.then if c.cond != 0 else c.other))


def render(e: E) -> String:
    return fp.match(e,
        lambda (n: Num) -> String: String(n.value),
        lambda (a: Add[String]) -> String: "(" + a.left + " + " + a.right + ")",
        lambda (m: Mul[String]) -> String: m.left + " * " + m.right,
        lambda (c: If[String, String]) -> String: "if " + c.cond + " then " + c.then + " else " + c.other)


def simplify(e: E) -> E:
    """Remove additions of zero and multiplications by one, bottom-up."""
    return fp.rewrite(e,
        fp.when[lambda (a: Add[E]) -> Bool: a.left == Num(0), lambda (a: Add[E]) -> E: a.right],
        fp.when[lambda (a: Add[E]) -> Bool: a.right == Num(0), lambda (a: Add[E]) -> E: a.left],
        fp.when[lambda (m: Mul[E]) -> Bool: m.left == Num(1), lambda (m: Mul[E]) -> E: m.right],
        fp.when[lambda (m: Mul[E]) -> Bool: m.right == Num(1), lambda (m: Mul[E]) -> E: m.left])


def main():
    var zero: E = Num(0)
    var one: E = Num(1)
    var x: E = Add(E(Mul(one, E(Num(6)))), E(Add(E(Num(4)), zero)))
    print(render(x), "=", evaluate(x))
    var y = simplify(x)
    print(render(y), "=", evaluate(y))

    # The branch not taken is never evaluated, however large it is.
    var big: E = one
    for _ in range(40):
        big = Mul(big, big)
    print(evaluate(E(If(zero, big, E(Num(7))))))

    # A value shared by both operands is evaluated once per match.
    var shared: E = Num(2)
    for _ in range(61):
        shared = Add(shared, shared)
    print(evaluate(shared))

    # Depth is limited only by memory.
    var deep: E = zero
    for _ in range(1_000_000):
        deep = Add(deep, one)
    print(evaluate(deep))

Run from the repository root pixi run mojo run -I src docs/examples/expression.mojo

Output

(1 * 6 + (4 + 0)) = 10
(6 + 4) = 10
7
4611686018427387904
1000000

x is Add(Mul(1, 6), Add(4, 0)). render(x) gives (1 * 6 + (4 + 0)), and evaluate(x) gives 10. simplify removes the multiplication by one and the addition of zero, so the simplified value renders as (6 + 4) and still evaluates to 10.

Declare recursive fields with R. Add[R] has two fields of type R. In Expr the layer passes R on, so a stored Add holds two Node[Expr] values. A constructor such as If[C, B] may take more than one parameter, so that a clause can treat the condition differently from the branches; the layer passes R to each.
Evaluate a child. The clause parameter Add[Int] asks for both fields as the result type: they arrive as the results of matching the two children with the same clauses. render asks for Add[String] and gets the rendered children.
Keep a child unevaluated. If[Int, E] asks for the condition evaluated and the branches as stored. The clause returns Next(...): the result of this value is the result of matching the chosen branch instead. The other branch is never evaluated, so If(zero, big, 7) returns 7 without evaluating big, a product of 2^40 ones.
Rewrite bottom-up. fp.rewrite transforms a value from the leaves up. Its clauses take the constructors that change, with recursive fields already rewritten, and return the new value. Every other value is rebuilt from its rewritten children, and a value whose children did not change is reused. A rewrite is one pass.
Share values. Node values are immutable, and copying one shares it, so Add(shared, shared) refers to one value twice. After 61 doublings of Num(2), evaluate(shared) returns 4611686018427387904, evaluating each shared value once per match.
Match deeply nested values. The match keeps pending values on an explicit stack and releases values in a loop. deep nests a million Add values, and evaluate(deep) returns 1000000 without a million native calls.

Lists and optional children¶

A recursive field may also be List[R] or Optional[R]:

file_tree.mojo Download

"""Recursive fields in a list or an optional: a folder holds entries, a shortcut may hold a target."""
import fp
from fp.adt import Data, Cases, Node, Value


@fieldwise_init
struct File(Copyable):
    var name: String
    var size: Int


@fieldwise_init
struct Folder[R: Value](Movable):
    var name: String
    var entries: List[Self.R]


@fieldwise_init
struct Shortcut[R: Value](Movable):
    var name: String
    var target: Optional[Self.R]


struct Tree(Data):
    comptime Layer[R: Value] = Cases[File, Folder[R], Shortcut[R]]


comptime T = Node[Tree]


def total_size(t: T) -> Int:
    """Every entry of a folder, and a shortcut's target when it has one, arrive evaluated."""
    return fp.match(t,
        lambda (f: File) -> Int: f.size,
        lambda (d: Folder[Int]) -> Int: sum_of(d.entries),
        lambda (l: Shortcut[Int]) -> Int: l.target.value() if l.target else 0)


def sum_of(sizes: List[Int]) -> Int:
    var total = 0
    for size in sizes:
        total += size
    return total


def listing(t: T) -> String:
    return fp.match(t,
        lambda (f: File) -> String: f.name,
        lambda (d: Folder[String]) -> String: d.name + "/{" + joined(d.entries) + "}",
        lambda (l: Shortcut[T]) -> String: l.name + "@")


def joined(items: List[String]) -> String:
    var text = String()
    for i in range(len(items)):
        text += (", " if i > 0 else "") + items[i]
    return text


def main():
    var notes: T = File("notes.txt", 120)
    var photos: T = Folder(String("photos"), [T(File("a.jpg", 2000)), T(File("b.jpg", 3000))])
    var home: T = Folder(String("home"), [notes, photos, T(Shortcut(String("latest"), Optional[T](photos))),
                                          T(Shortcut(String("broken"), Optional[T](None)))])
    print(listing(home))
    print(total_size(home))

Run from the repository root pixi run mojo run -I src docs/examples/file_tree.mojo

Output

home/{notes.txt, photos/{a.jpg, b.jpg}, latest@, broken@}
10120

Folder[Int] receives the sizes of all its entries, and Shortcut[Int] the size of its target when it has one. home holds notes.txt (120), photos (5000), a shortcut to photos (5000) and a shortcut with no target (0), so total_size(home) returns 10120. listing takes Shortcut[T], the field as stored, so it prints latest@ without following the shortcut.

Why every match ends¶

A Node can refer only to values that already exist, and it never changes, so every value is a finite acyclic graph. Structural recursion evaluates children of the current value; Next must continue with a value of smaller height. These rules make the matching traversal terminate. A clause's own loops or additional matches remain ordinary Mojo code. See guarantees and their sources for the termination argument and the runtime check on Next.

The next chapter combines these pieces in a configuration processor.