<!-- Generics · Tin · https://tin.ad/docs/learn/generics/ · generated from the built page -->

[Learn](https://tin.ad/docs/learn/) · The language · 10 of 34

# Generics

**Goal.** Write one function or type for many element types, and say what a type must support.

## 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.tin · tin run why.tin*

```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]))
}
```

<!-- output -->
```text
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.tin · tin run largest.tin*

```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)
}
```

<!-- output -->
```text
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.tin · tin check not-comparable.tin*

```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 }]))
}
```

<!-- compiler output -->
```text
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.tin · tin run traits.tin*

```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)
}
```

<!-- output -->
```text
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.tin · tin check traits-missing.tin*

```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 }))
}
```

<!-- compiler output -->
```text
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.tin · tin run ord.tin*

```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])
}
```

<!-- output -->
```text
[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.tin · tin run generic-type.tin*

```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))
}
```

<!-- output -->
```text
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.tin · tin run generic-sum.tin*

```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))
}
```

<!-- output -->
```text
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.tin · tin check infer.tin*

```tin
type Tree<T> = | Leaf | Node(Tree<T>, T, Tree<T>)

fn main() {
  let t = Node(Leaf, "a", Leaf)
}
```

<!-- compiler output -->
```text
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[]`.

Your answer   Checking needs JavaScript; the solution below works without it.

**Solution

*task-1.solution.tin · tin run task-1.solution.tin*

```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))
}
```

<!-- output -->
```text
["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.

Your answer   Checking needs JavaScript; the solution below works without it.

**Solution

*task-2.solution.tin · tin run task-2.solution.tin*

```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()}")
}
```

<!-- output -->
```text
number: 42
word: tin
```

### Task 3: Walk the tree · harder

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.

Your answer   Checking needs JavaScript; the solution below works without it.

**Solution

*task-3.solution.tin · tin run task-3.solution.tin*

```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))
}
```

<!-- output -->
```text
[1, 2, 3, 4]
```

## Recap

- Type parameters go in `<T>`.
- Each use is checked with the real type.
- Traits say what `T` must be able to do.

In the reference: [Generics](https://tin.ad/docs/ref/language/#generics) · [Traits](https://tin.ad/docs/ref/language/#traits)
