Recursive and Mutually Recursive Types

This example builds and evaluates a tiny expression tree containing numbers, additions, and blocks of statements. The two top-level types, Expr and Stmt, demonstrate both recursion and mutual recursion without needing an enclosing type.

Expr := [Number(I64), Add(Expr, Expr), Block(List(Stmt))].{
	eval : Expr -> I64
	eval = |expr| match expr {
		Number(n) => n
		Add(left, right) => eval(left) + eval(right)
		Block(statements) => statements.fold(
			0,
			|_, statement| match statement {
				Stmt.Yield(value) => eval(value)
			},
		)
	}
}

Stmt := [Yield(Expr)]

expression : Expr
expression = Block([Stmt.Yield(Add(Number(20), Number(22)))])

expect Expr.eval(expression) == 42
expect Expr.eval(Block([])) == 0

Expr refers to itself through the two operands of Add. It also refers to Stmt through Block, while Stmt refers back to Expr through Yield. Together, those references let us nest expressions inside statements and statements inside expressions.

Every type in a recursive cycle must be nominal (:= or ::). A type alias (:) cannot be used to define such a cycle.

For an example of grouping related types within a type module, see Nested Types.

Output

Run this from the directory that has main.roc in it:

$ roc test main.roc

All (2) tests passed in 10.9 ms.

Validated with Roc nightly-2026-10-29-a0a9fc2.