Sn Tin

Learn Tin · Part 1: The language · Chapter 10

Generics

One function or type for many element types.

One function for many types

Some functions don't care what's inside an array. Taking the first item works the same for ints, strings or anything else. A type parameter in <T> says "some type, chosen by whoever calls me":

why.tintin run why.tin
// Without generics you'd write the same function once per type:
fn firstInt(xs: int[]): Option<int> => if xs.len == 0 { None } else { Some(xs[0]) }
fn firstString(xs: string[]): Option<string> => if xs.len == 0 { None } else { Some(xs[0]) }

// With a type parameter T, one function works for any element type.
fn firstOf<T>(xs: T[]): Option<T> => if xs.len == 0 { None } else { Some(xs[0]) }

fn main() {
  print(firstInt([1, 2]))
  print(firstString(["a"]))
  print(firstOf([1, 2]))         // T is int here
  print(firstOf(["a"]))          // and string here
  print(firstOf([true, false]))
}
Some(1)
Some("a")
Some(1)
Some("a")
Some(true)

You never write firstOf<int>(...). Tin works out T from the arguments.

Checked for each use

Here is a largest that works for any type you can compare with >:

largest.tintin run largest.tin
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() {
  print(largest([3, 9, 4]))
  print(largest([2.5, -1.0]))
  print(largest(["pear", "apple", "plum"]))   // strings compare alphabetically
  let nothing: Option<int> = largest([])     // here the type comes from the annotation
  print(nothing)
}
Some(9)
Some(2.5)
Some("plum")
None

Tin checks a generic function again for each type it's used with. A struct has no order until you give it one, so calling largest on points fails. The error points at the line that breaks and says which type it was compiling for:

not-comparable.tintin check not-comparable.tin
type Point = { x: int, y: int }

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() {
  print(largest([Point { x: 1, y: 2 }, Point { x: 3, y: 0 }]))
}
error: '>' is not defined for Point: it has no order
 --> not-comparable.tin:7:8
  |
7 |     if x > best { best = x }
  |        ^^^^^^^^
  = note: give it one with a compare method (the Ord trait): negative if a comes first, 0 if equal, positive after
  = note:   fn Point.compare(a: Point, b: Point): int
  = note: or compare a field: `a.x < b.x`
  = note: while compiling largest<Point>
  = fix: add Point.compare

Each use is also compiled to its own code, so a generic function is as fast as one written for that type by hand.

Say what you need: traits

That error comes from inside largest, which is fine for your own code and annoying for code someone else wrote. A trait lists the methods a type parameter needs, and T: Shape asks for them up front. Any type that has those methods fits; you don't declare that it does.

traits.tintin run traits.tin
trait Shape {
  fn area(s: Self): float
}

type Circle = { r: float }
type Square = { side: float }

fn Circle.area(c: Circle): float => PI * c.r * c.r
fn Square.area(s: Square): float => s.side * s.side

fn bigger<T: Shape>(a: T, b: T): T => if a.area() > b.area() { a } else { b }

fn main() {
  print(bigger(Square { side: 2.0 }, Square { side: 3.0 }))
  print(bigger(Circle { r: 1.0 }, Circle { r: 0.5 }).r)
}
Square { side: 3.0 }
1.0

Now a type without area is rejected at the call, and the error names the method to write. tin fix adds it as a stub for you:

traits-missing.tintin check traits-missing.tin
trait Shape {
  fn area(s: Self): float
}

type Tri = { b: float, h: float }

fn bigger<T: Shape>(a: T, b: T): T => if a.area() > b.area() { a } else { b }

fn main() {
  print(bigger(Tri { b: 1.0, h: 2.0 }, Tri { b: 2.0, h: 2.0 }))
}
error: Tri does not satisfy Shape: it has no method 'area'
  --> traits-missing.tin:10:16
   |
10 |   print(bigger(Tri { b: 1.0, h: 2.0 }, Tri { b: 2.0, h: 2.0 }))
   |                ^^^^^^^^^^^^^^^^^^^^^^
   = note: bigger<T: Shape> needs it; a type satisfies a trait by having its methods:
   = note:   fn Tri.area(s: Tri): float
   = fix: add the method

A bound works in the other direction too. Inside bigger, T has only what Shape promises, so calling a method Shape doesn't list is an error right there, before anyone calls bigger.

The standard library has three traits of its own. Ord asks for compare: give a type that method and it works with <, sort, min and max. Show (show) and Eq (equals) every type already has; write your own to change how it prints or what == means:

ord.tintin run ord.tin
type Version = { major: int, minor: int }

fn Version.compare(a: Version, b: Version): int {
  if a.major != b.major { a.major - b.major } else { a.minor - b.minor }
}

fn Version.show(v: Version): string => "v{v.major}.{v.minor}"

fn main() {
  let vs = [Version { major: 1, minor: 4 }, Version { major: 0, minor: 9 }, Version { major: 1, minor: 0 }]
  print(sort(vs))
  print(max(vs[0], vs[2]))
  print(vs[1] < vs[2])
}
[v0.9, v1.0, v1.4]
v1.4
true

A trait is not a type: there is no array of "any Shape". For values of different kinds in one array, use an enum, as in the Enums chapter.

Generic types

Types take parameters the same way. You've already used two: Option<T> and Result<T, E> are ordinary generic sum types from the standard library.

generic-type.tintin run generic-type.tin
// Types can take parameters too. Option<T> and Result<T, E> are written this way.
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 main() {
  let p = Pair { first: 1, second: "one" }
  print(p)
  print(swap(p))
}
Pair { first: 1, second: "one" }
Pair { first: "one", second: 1 }

A generic sum type can contain itself. Here is a tree that holds any type of item:

generic-sum.tintin run generic-sum.tin
// A generic sum type: a tree of anything.
type Tree<T> = | Leaf | Node(Tree<T>, T, Tree<T>)

fn size<T>(t: Tree<T>): int => match t {
  Leaf => 0
  Node(left, _, right) => size(left) + 1 + size(right)
}

fn main() {
  let t: Tree<string> = Node(Node(Leaf, "a", Leaf), "b", Node(Leaf, "c", Leaf))
  print(size(t))
}
3

Notice the : Tree<string>. A bare Leaf says nothing about T, and today Tin doesn't look at the other arguments to work it out, so it asks you to say so:

infer.tintin check infer.tin
type Tree<T> = | Leaf | Node(Tree<T>, T, Tree<T>)

fn main() {
  let t = Node(Leaf, "a", Leaf)
}
error: cannot infer the type parameter T of Tree here
 --> infer.tin:4:16
  |
4 |   let t = Node(Leaf, "a", Leaf)
  |                ^^^^
  = note: nothing here says what T is; write the full type: `let x: Tree<...> = ...`

Tasks

●○○ Task 1: Repeat anything

Write repeatItem<T>(item: T, times: int): T[].

Solution
task-1.solution.tintin run task-1.solution.tin
fn repeatItem<T>(item: T, times: int): T[] {
  var out: T[] = []
  for i in 0..times {
    out.push(item)
  }
  out
}

fn main() {
  print(repeatItem("hi", 3))
  print(repeatItem(0, 4))
}
["hi", "hi", "hi"]
[0, 0, 0, 0]

●●○ Task 2: A labelled box

Declare Box<T> with a label and an item, add a method open that returns the item, and use it with a number and a string.

Solution
task-2.solution.tintin run task-2.solution.tin
type Box<T> = { label: string, item: T }

fn Box.open<T>(b: Box<T>): T => b.item

fn main() {
  let a = Box { label: "number", item: 42 }
  let b = Box { label: "word", item: "tin" }
  print("{a.label}: {a.open()}")
  print("{b.label}: {b.open()}")
}
number: 42
word: tin

●●● Task 3: Walk the tree

Using the Tree<T> above, write items<T>(t: Tree<T>): T[] that lists every item from left to right. Hint: xs.concat(ys) joins two arrays.

Solution
task-3.solution.tintin run task-3.solution.tin
type Tree<T> = | Leaf | Node(Tree<T>, T, Tree<T>)

// Items left to right: everything in the left branch, then this item, then the right branch.
fn items<T>(t: Tree<T>): T[] => match t {
  Leaf => []
  Node(left, item, right) => items(left).concat([item]).concat(items(right))
}

fn main() {
  let t: Tree<int> = Node(Node(Leaf, 1, Leaf), 2, Node(Leaf, 3, Node(Leaf, 4, Leaf)))
  print(items(t))
}
[1, 2, 3, 4]

What's next

Next: Values, var and inout. Every value is a copy. How you change things anyway, and why it helps.

In the reference: Generics · Traits