Tutorial

4. Algebraic data and pattern matching¶

An algebraic data type describes a value through its possible constructors and the fields each constructor carries. A shape, for example, can be a circle with a radius, a rectangle with two sides, or a dot with no fields. The choice of constructor is a sum type; the fields within a constructor form a product.

Pattern matching handles each constructor with a clause. fp.match checks exhaustiveness at compile time, so leaving a constructor uncovered is an error. Clauses are plain functions or lambdas without captures. Pass any additional data through a context or as another matched value.

Declare a type and match it¶

shapes.mojo Download

"""A sum type without recursion: clauses, a guard, a context and a pair of values."""
import fp
from fp.adt import Data, Cases, Node, Value


@fieldwise_init
struct Circle(Copyable):
    var radius: Float64


@fieldwise_init
struct Rect(Copyable):
    var width: Float64
    var height: Float64


@fieldwise_init
struct Dot(Copyable):
    pass


struct Shape(Data):
    comptime Layer[R: Value] = Cases[Circle, Rect, Dot]


comptime S = Node[Shape]


def area(s: S) -> Float64:
    return fp.match(s,
        lambda (c: Circle) -> Float64: 3.0 * c.radius * c.radius,
        lambda (r: Rect) -> Float64: r.width * r.height,
        lambda (d: Dot) -> Float64: 0.0)


def describe(s: S) -> String:
    """A guarded clause applies only when its guard holds; the next clause covers the rest."""
    return fp.match(s,
        fp.when[lambda (r: Rect) -> Bool: r.width == r.height, lambda (r: Rect) -> String: "a square"],
        lambda (r: Rect) -> String: "a rectangle",
        lambda (c: Circle) -> String: "a circle",
        lambda (s: S) -> String: "something else")


def scaled_area(s: S, factor: Float64) -> Float64:
    """The context reaches every clause as its second parameter."""
    return fp.match(s,
        lambda (c: Circle, k: Float64) -> Float64: 3.0 * c.radius * c.radius * k * k,
        lambda (r: Rect, k: Float64) -> Float64: r.width * r.height * k * k,
        lambda (d: Dot, k: Float64) -> Float64: 0.0,
        context=factor)


def same_kind(a: S, b: S) -> Bool:
    """Two values matched together; the last clause takes every other combination."""
    return fp.match((a, b),
        lambda (x: Circle, y: Circle) -> Bool: True,
        lambda (x: Rect, y: Rect) -> Bool: True,
        lambda (x: Dot, y: Dot) -> Bool: True,
        lambda (x: S, y: S) -> Bool: False)


def main():
    var shapes: List[S] = [S(Circle(1.0)), S(Rect(2.0, 3.0)), S(Rect(2.0, 2.0)), S(Dot())]
    for s in shapes:
        print(describe(s), area(s), scaled_area(s, 2.0))
    print(same_kind(shapes[1], shapes[2]), same_kind(shapes[0], shapes[3]))

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

Output

a circle 3.0 12.0
a rectangle 6.0 24.0
a square 4.0 16.0
something else 0.0 0.0
True False

The program prints one line per shape: a circle 3.0 12.0, a rectangle 6.0 24.0, a square 4.0 16.0 and something else 0.0 0.0.

Constructors are ordinary structs. Circle, Rect and Dot are @fieldwise_init structs. Shape lists them in a Cases, and Node[Shape] holds one of them. A constructor converts to a Node implicitly, so S(Circle(1.0)) and var s: S = Dot() both work.
A clause's parameter type selects its constructor. fp.match(s, ...) calls the clause for the constructor s holds and returns its result. Every clause returns the same type: area returns 3.0 for Circle(1.0).
Every constructor must be handled. Leave out the Dot clause in area and the program does not compile: fp.match: constructor Dot has no clause that cannot decline.
A parameter of the whole type is a catch-all. In describe, the last clause takes S and handles every constructor that no earlier clause handled, so Dot() gives "something else".

Add a guard to a clause¶

fp.when[guard, clause] is a clause that applies only when guard returns True for the same argument. When it returns False, the next clause for that constructor is tried. In describe, the square clause takes Rect(2.0, 2.0) but declines Rect(2.0, 3.0), whose sides differ, and the plain Rect clause returns "a rectangle". A guarded clause alone never covers a constructor, so the plain Rect clause is required.

Clauses are tried in the order written, and the first that applies is used. A clause that can never be selected, because an earlier clause for the same constructor cannot decline, is a compile-time error.

Pass data through a context¶

Clauses do not capture variables. Pass data that every clause needs, such as a scale factor or an environment, with context=; it arrives as each clause's second parameter. scaled_area(s, 2.0) multiplies each area by 2.0 * 2.0, so the circle's 3.0 becomes 12.0. The match borrows the context.

Several values at once¶

fp.match((a, b), ...) matches two values together, and (a, b, c) three. Each clause takes one parameter per value, and the first clause whose parameters all apply is used. In shapes.mojo, same_kind returns True for two rectangles and False for a circle and a dot.

traffic_light.mojo Download

"""Matching several values together: a light's next state for an event, and a third plain value."""
import fp
from fp.adt import Data, Cases, Node, Value


@fieldwise_init
struct Red(Copyable):
    pass


@fieldwise_init
struct Green(Copyable):
    pass


@fieldwise_init
struct Amber(Copyable):
    pass


struct Light(Data):
    comptime Layer[R: Value] = Cases[Red, Green, Amber]


@fieldwise_init
struct Tick(Copyable):
    pass


@fieldwise_init
struct Outage(Copyable):
    var code: Int


struct Event(Data):
    comptime Layer[R: Value] = Cases[Tick, Outage]


comptime L = Node[Light]
comptime V = Node[Event]


def step(light: L, event: V) -> L:
    return fp.match((light, event),
        lambda (s: Red, e: Tick) -> L: Green(),
        lambda (s: Green, e: Tick) -> L: Amber(),
        lambda (s: Amber, e: Tick) -> L: Red(),
        lambda (s: L, e: Outage) -> L: Red())


def name(light: L) -> String:
    return fp.match(light,
        lambda (r: Red) -> String: "red",
        lambda (g: Green) -> String: "green",
        lambda (a: Amber) -> String: "amber")


def report(light: L, event: V, waiting: Int) -> String:
    """A plain third value takes part in guards like the others."""
    return fp.match((light, event, waiting),
        fp.when[lambda (s: Red, e: Tick, n: Int) -> Bool: n > 3,
                lambda (s: Red, e: Tick, n: Int) -> String: "red with a queue of " + String(n)],
        lambda (s: L, e: Outage, n: Int) -> String: "outage " + String(e.code),
        lambda (s: L, e: V, n: Int) -> String: "normal")


def main():
    var light: L = Red()
    var tick: V = Tick()
    for _ in range(4):
        light = step(light, tick)
        print(name(light))
    print(name(step(light, V(Outage(7)))))
    print(report(L(Red()), tick, 5), "|", report(light, V(Outage(7)), 0), "|", report(light, tick, 0))

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

Output

green
amber
red
green
red
red with a queue of 5 | outage 7 | normal

step combines a light with an event. Starting from red, four ticks give green, amber, red and green, and its last clause turns an outage into red in any state. Every combination of constructors must be covered.

In report, the third value is a plain Int. A value that is not a Node takes part as it is, and guards can test it: report(L(Red()), tick, 5) returns "red with a queue of 5" because the guard n > 3 holds, while a green light with a tick and 0 reaches the last clause, "normal".

Raise from a clause¶

A clause may raise. Every clause raises nothing or one common error type, and the match raises that type unchanged; the first raise stops the match. The job router dispatches through guarded clauses that raise a typed error.

The architecture chapter explains how coverage is checked. Next, store non-recursive algebraic data types in place and match Result and Optional with the same clause syntax.