Chapter 5 of 8
Generics
Generic code is specialised at compile time. Stack<int> and Stack<string> become separate WebAssembly functions.
tin run examples/06-generics.tin// Generics are monomorphised: Stack<int> and Stack<string> each compile to
// their own specialised WebAssembly, with no boxing and no runtime type checks.
type Stack<T> = { items: T[] }
fn newStack<T>(): Stack<T> {
Stack { items: [] }
}
fn Stack.push<T>(s: inout Stack<T>, item: T) {
s.items.push(item)
}
fn Stack.pop<T>(s: inout Stack<T>): Option<T> {
if s.items.len == 0 { None } else { Some(s.items.pop()) }
}
type Pair<A, B> = { first: A, second: B }
fn swap<A, B>(p: Pair<A, B>): Pair<B, A> => Pair { first: p.second, second: p.first }
fn largest<T>(xs: T[]): Option<T> {
if xs.len == 0 { return None }
var best = xs[0]
for x in xs {
if x > best { best = x }
}
Some(best)
}
fn main() {
var numbers: Stack<int> = newStack()
numbers.push(1)
numbers.push(2)
numbers.push(3)
print(numbers.pop())
print(numbers.pop())
var words: Stack<string> = newStack()
words.push("tin")
print(words.pop())
print(words.pop())
let p = Pair { first: "answer", second: 42 }
print(p)
print(swap(p))
print(largest([3, 9, 4]))
print(largest([2.5, 1.5]))
print(largest(["pear", "apple", "zebra"]))
} Some(3)
Some(2)
Some("tin")
None
Pair { first: "answer", second: 42 }
Pair { first: 42, second: "answer" }
Some(9)
Some(2.5)
Some("zebra") There's no boxing and no runtime type check: the checker monomorphises each use. Recursive sum types work the same way, which is how the next example builds an immutable tree.
tin run examples/07-tree.tin// A recursive sum type: an immutable binary search tree.
type Tree =
| Leaf
| Node { left: Tree, value: int, right: Tree }
fn insert(t: Tree, v: int): Tree => match t {
Leaf => Node { left: Leaf, value: v, right: Leaf }
Node { left, value, right } =>
if v < value { Node { left: insert(left, v), value, right } }
else if v > value { Node { left, value, right: insert(right, v) } }
else { t }
}
fn contains(t: Tree, v: int): bool => match t {
Leaf => false
Node { left, value, right } =>
if v == value { true } else if v < value { contains(left, v) } else { contains(right, v) }
}
fn depth(t: Tree): int => match t {
Leaf => 0
Node { left, right } => 1 + max(depth(left), depth(right))
}
fn inOrder(t: Tree, out: inout int[]) {
match t {
Leaf => {}
Node { left, value, right } => {
inOrder(left, &out)
out.push(value)
inOrder(right, &out)
}
}
}
fn main() {
var tree: Tree = Leaf
for v in [50, 30, 70, 20, 40, 60, 80, 30] {
tree = insert(tree, v)
}
var sorted: int[] = []
inOrder(tree, &sorted)
print(sorted)
print("depth: {depth(tree)}")
print("contains 60? {contains(tree, 60)}")
print("contains 65? {contains(tree, 65)}")
} [20, 30, 40, 50, 60, 70, 80]
depth: 3
contains 60? true
contains 65? false