kaikai
ES
The book

Chapter 4 · Compound Types

The primitive types from the previous chapter are raw pieces. To build real programs you glue them into structures: aggregates with named fields, lists, tuples, and the two stdlib types you’ll reach for more than any other, Option and Result.

The sum types (type Tag = Foo | Bar(Int)) you saw in the tour get a chapter of their own, chapter 5.

4.1 Records

A record is an aggregate with named fields. You declare it with type and braces:

type Point = { x: Int, y: Int }

type Employee = {
  name: String,
  age: Int,
  salary: Int,
}

The trailing comma is optional but idiomatic: adding a field doesn’t touch the previous line, so the diff stays clean.

To build a value, write the type name and the fields in braces:

let origin = Point { x: 0, y: 0 }
let p      = Point { x: 3, y: 4 }
let ada    = Employee { name: "Ada", age: 30, salary: 1500 }

To read a field, you use .:

println("p is at (#{p.x}, #{p.y})")
println("#{ada.name} is #{ada.age}")

That’s enough for the day-to-day. Three more details:

  • Records are immutable. p.x = 7 does not exist. If you need a point with one different field, you build a new one with the spread sugar:

    let p  = Point { x: 3, y: 4 }
let p2 = Point { ...p, x: 7 }    # Point { x: 7, y: 4 }

    ...p copies all fields of p; the named initializers after it (here x: 7) override what they repeat. It’s the list spread of §4.3, applied to records.

  • Records are nominal. Point { x: Int, y: Int } and another Position { x: Int, y: Int } are distinct types even though they have the same shape. I wanted it that way: if you want a position, say position.

  • Spread has rules. Only one spread per literal, and it must come first — Point { x: 7, ...p } is a parse error. The initializers that follow must be named (x: expr), not punned or positional. These are deliberate: they make it obvious who wins on a duplicate.

Declaration, construction, access and functional update in one program:

# examples/ch04/01_records.kai
type Point = { x: Int, y: Int }

type Employee = {
  name: String,
  age: Int,
  salary: Int
}

fn distance(a: Point, b: Point) : Int {
  let dx = a.x - b.x
  let dy = a.y - b.y
  dx * dx + dy * dy
}

fn main() {
  let origin = Point { x: 0, y: 0 }
  let p = Point { x: 3, y: 4 }

  println("origin.x = #{origin.x}, origin.y = #{origin.y}")
  println("p at (#{p.x}, #{p.y})")
  println("distance² = #{distance(origin, p)}")

  # Functional update with `...`: copies all fields and
  # overrides the named ones.
  let p2 = Point { ...p, x: 7 }
  println("p2 at (#{p2.x}, #{p2.y})")

  let ada = Employee { name: "Ada", age: 30, salary: 1500 }
  println("#{ada.name} is #{ada.age}, salary #{ada.salary}")

  # Promotion: same employee, new salary.
  let ada_post = Employee { ...ada, salary: 2200 }
  println("#{ada_post.name} now earns #{ada_post.salary}")
}
$ kai run examples/ch04/01_records.kai
origin.x = 0, origin.y = 0
p at (3, 4)
distance² = 25
p2 at (7, 4)
Ada is 30, salary 1500
Ada now earns 2200

4.1.1 Private fields

Record fields are public by default: any module that imports the type can read them and name them in a literal. priv in front of a field name flips that default:

# module `safe`
pub type Account = {
  name:         String,    # public by default
  priv balance: Real,      # private to module `safe`
}

pub fn open(name: String) : Account =
  Account { name: name, balance: 0.0 }

pub fn deposit(a: Account, amount: Real) : Account =
  Account { ...a, balance: a.balance + amount }

pub fn balance_of(a: Account) : Real = a.balance

From inside the safe module, the balance field reads and writes like any other. From outside, it doesn’t:

import safe

fn main() {
  let a = safe.open("savings")
  println("#{a.name}")            # OK, `name` is public
  println("#{safe.balance_of(a)}")  # OK, going through the getter

  # The next two lines don't compile:
  # println("#{a.balance}")          # ← field `balance` of `Account` is private to module `safe`
  # let d = safe.Account {            # ← cannot construct `Account` from outside …
  #   name: "x",
  #   balance: 1000.0,
  # }
}

The rule is strict: no external reads, no mention inside a construction literal. If module safe wants others to create accounts, it exposes constructors (open) and operations (deposit) that preserve the invariants; the raw field stays hidden.

The record becomes a lightweight abstract type: public shape, interior under the author’s control. You’ll use it that way in ch. 17 to hide the store actor’s state, and in ch. 18 so ledger balances can’t be constructed from outside the domain module.

The type with a private field and its operations, in a single file. Inside the module that declares it, priv restricts nothing: the rejected lines above fail only from another module, and ch. 8 shows them with two files.

# examples/ch04/06_priv.kai
type Account = {
  name: String,
  priv balance: Real
}

fn open(name: String) : Account =
  Account { name: name, balance: 0.0 }

fn deposit(a: Account, amount: Real) : Account =
  Account { ...a, balance: a.balance + amount }

fn balance_of(a: Account) : Real = a.balance

fn main() {
  let a0 = open("savings")
  let a1 = deposit(a0, 100.0)
  let a2 = deposit(a1, 50.0)
  println("#{a2.name}: #{balance_of(a2)}")
}
$ kai run examples/ch04/06_priv.kai
savings: 150

4.2 Field access and destructuring

For one or two fields, . is fine. When you need several at once, destructuring is cleaner:

fn distance_squared(a: Point, b: Point) : Int {
  let Point { x: ax, y: ay } = a
  let Point { x: bx, y: by } = b
  let dx = ax - bx
  let dy = ay - by
  dx * dx + dy * dy
}

When the field names work as variables, drop the : and each field binds to a variable of the same name:

fn describe(p: Point) : String {
  let Point { x, y } = p
  "(#{x}, #{y})"
}

Destructuring pays off most in match, where you decide what to do based on the values of the fields:

fn classify(p: Point) : String =
  match p {
    Point { x: 0, y: 0 } -> "origin"
    Point { x: 0, y: _ } -> "Y axis"
    Point { x: _, y: 0 } -> "X axis"
    Point { x, y }       -> "point at (#{x}, #{y})"
  }

The compiler checks exhaustiveness, just like with sum types. Over Int fields it’s covered by the final Point { x, y } arm, which matches any Point; remove that arm and it stops compiling.

The three ways of opening a record, one after the other:

# examples/ch04/02_destructuring.kai
type Point = { x: Int, y: Int }

fn describe(p: Point) : String {
  let Point { x, y } = p
  "(#{x}, #{y})"
}

fn classify(p: Point) : String =
  match p {
    Point { x: 0, y: 0 } -> "origin"
    Point { x: 0, y: _ } -> "Y axis"
    Point { x: _, y: 0 } -> "X axis"
    Point { x, y } -> "point at (#{x}, #{y})"
  }

fn main() {
  println(describe(Point { x: 3, y: 4 }))
  println(classify(Point { x: 0, y: 0 }))
  println(classify(Point { x: 0, y: 7 }))
  println(classify(Point { x: 5, y: 0 }))
  println(classify(Point { x: 2, y: 9 }))
}
$ kai run examples/ch04/02_destructuring.kai
(3, 4)
origin
Y axis
X axis
point at (2, 9)

4.3 Lists

A list is an immutable, linked sequence of values of the same type. The type is written with brackets around the element type: [Int], [String], [Point], [[String]] (list of lists).

Building literals:

let primes = [2, 3, 5, 7, 11]
let empty: [Int] = []

kaikai also has range literals, which the type system treats as just another list:

let r1 = [1..10]        # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
let r2 = [1, 3..10]     # [1, 3, 5, 7, 9]
let r3 = [10, 9..1]     # [10, 9, 8, ..., 1]

The last two carry a step, and the step isn’t written: it’s read off the first two elements. [1, 3..10] moves by two because 3 - 1 is two, and [10, 9..1] counts down because the subtraction comes out negative. It’s the Haskell form, and it has one advantage over annotating the step separately: the first two elements you read are the ones you get.

One cost detail: the range is lazy. The runtime stores it as three numbers (start, end, step), not ten cells, and elements are generated only when something consumes them. [1..1_000_000] |> list.sum never materializes a million cells; to your code it is indistinguishable from the handwritten list.

To extend an existing list, use ... (spread):

let xs = [1, 2, 3]
let ys = [0, ...xs, 99]      # [0, 1, 2, 3, 99]

Unlike record spread, list spread takes any number of spreads, anywhere in the literal: [...a, ...b] works, and so does [...a, 9, ...b, 10].

Reach for it when you’re putting an element on the front. The exact same list comes out of [h] ++ t:

fn prepend(h: Int, t: [Int]) : [Int] = [h, ...t]
fn prepend_concat(h: Int, t: [Int]) : [Int] = [h] ++ t

[h, ...t] says “a list starting with h and continuing with t” — the same shape as the pattern you’ll take it apart with later — and emits the cons directly. [h] ++ t says “glue these two lists”, and to do that it builds a one-element list whose only purpose is to be glued: one allocation per call.

Measuring it has a catch. Put both forms in a bench whose body discards the result and each iteration costs less than the clock’s resolution, so the report hands you noise (§7.4 shows how to spot it). With the result consumed, built with --release, three million iterations over an eight-element tail, on my machine: 0.05 s for the spread against 0.11 s for the concat.

kai lint flags the second form as list_concat_literal_to_spread.

None of which is an argument against ++. Concatenating two lists that both already exist is exactly what it’s for.

To take them apart, the patterns of match:

fn sum(xs: [Int]) : Int =
  match xs {
    [] -> 0
    [h, ...t] -> h + sum(t)
  }

[] matches the empty list. [h, ...t] matches any non-empty list, binding h to the first element (“head”) and t to the rest (“tail”). Between them they cover every case, so the match is exhaustive.

More specific patterns are also legal:

match xs {
  []                       -> "empty"
  [only]                   -> "one: #{only}"
  [first, second, ...]     -> "at least two"
}

[] and [h, ...t] already cover any list; to single out “exactly one element”, write [only] before the catch-all.

A language convention: if the tail matters, give it a name — [h, ...t] and then use t. If it doesn’t, write ... alone, no name — [h, ...]. It’s the difference between “I take the head, the rest I keep for later” and “I take the head, the rest I discard”. An invented name that goes unused is noise; the bare form states the intent without one.

For indexed access, the stdlib exposes list.nth:

let first  = list.nth(xs, 0)    # Option[Int]
let third  = list.nth(xs, 2)    # Option[Int]

Notice the return type: Option[a], not a. Ask for element 99 of a list of three and there is no value to return; the type forces you to consider it. It’s the same idea as Option and Result, which you’ll put to work in §4.5: kaikai prefers to enclose the possibility of failure in the type rather than abort at runtime.

Two more things about indexed access. It is O(n) — lists are linked, not indexed; walking to position i costs i steps. For random access there are two other types: Vec[T], coming up in a moment, and Array[T], which you’ll meet in chapter 12.

And the syntax xs[i] that some languages use for lists is a type error on a list — indexing is for Vec and Array. xs[i] suggests cheap, guaranteed access, which would be lying about a linked list.

For most code, you don’t want to index by hand anyway. Recursion over [h, ...t] or the higher-order functions of chapter 6 (map, filter, reduce) are the natural way to process lists.

Lists are immutable. There is no xs[0] = 99. If you need a modified list, you build a new one.

Construction, ranges, recursive traversal and patterns in a single program:

# examples/ch04/03_lists.kai
fn sum(xs: [Int]) : Int =
  match xs {
    [] -> 0
    [h, ...t] -> h + sum(t)
  }

fn length[a](xs: [a]) : Int =
  match xs {
    [] -> 0
    [_, ...t] -> 1 + length(t)
  }

fn main() {
  let primes = [2, 3, 5, 7, 11]
  let r = [1..10]  # [1, ..., 10]
  let evens = [2, 4..20]  # [2, 4, ..., 20]
  let combo = [0, ...primes, 13]  # spread

  println("primes: length=#{length(primes)}, sum=#{sum(primes)}")
  println("r:      length=#{length(r)}, sum=#{sum(r)}")
  println("evens:  length=#{length(evens)}, sum=#{sum(evens)}")
  println("combo:  length=#{length(combo)}, sum=#{sum(combo)}")
}
$ kai run examples/ch04/03_lists.kai
primes: length=5, sum=28
r:      length=10, sum=55
evens:  length=10, sum=110
combo:  length=7, sum=41

Vec[T] — indexing without giving up values

When you genuinely need to index, the answer is Vec[T]: a flat, contiguous buffer with O(1) access that behaves like a value. Not one of its operations carries Mutable in its row.

The operations live in collections.vec and you call them qualified. They are the ones you’d expect: vec.get, vec.set, vec.push, vec.length, vec.slice, vec.map, vec.flat_map, vec.filter, vec.foldl, vec.from_list and vec.to_list. The a[1] in the example is shorthand for vec.get(a, 1). The pipes of chapter 6 run over a Vec just as they do over a list: | dispatches to vec.map, || to vec.flat_map, |? to vec.filter and |! to vec.each.

A list literal in a Vec position builds the vector directly, with no linked list in between. And the interesting part is how they write: set and push return the resulting vector rather than modifying the one they get.

# examples/ch04/11_vec.kai
import collections.vec

fn main() : Unit / Stdout = {
  let a: Vec[Int] = [10, 20, 30]
  println("a[1] = #{a[1]}, same as vec.get(a, 1) = #{vec.get(a, 1)}")

  # `set` and `push` return the resulting vector; `a` is untouched.
  let b = vec.push(vec.set(a, 1, 99), 40)
  println("a = #{vec.to_list(a)}")
  println("b = #{vec.to_list(b)}")
}
$ kai run examples/ch04/11_vec.kai
a[1] = 20, same as vec.get(a, 1) = 20
a = [10, 20, 30]
b = [10, 99, 30, 40]

The annotation is what decides: that same bare [10, 20, 30], without the : Vec[Int], is still a linked list.

Notice that a didn’t change. That’s the guarantee, and it has no exceptions: no name pointing at a Vec ever sees what another one writes.

The guarantee isn’t paid for with a copy per write. The runtime checks whether the buffer is shared — the same reference counting as chapter 13 — and writes in place when it has a single owner. In the example a is used after the set (the next line prints it), so at the moment of the write it is shared and the write copies. Thread the vector linearly instead, accumulator style, where each step is the sole owner of what it receives, and nothing is copied: building it asks for memory once.

A slice is a constant-cost view: a[1..2] copies no elements, it shares the buffer. Both ends are included, as in a range literal.

And Array[T], which shows up in chapter 12, is the other face: the mutable reference, where writes are observable through every alias and each one demands / Mutable. The rule is short: Vec when you want a collection that behaves like a value, Array when you want genuine shared mutation.

4.4 Strings, not lists of chars

Many languages mix these two up. In kaikai, a String is not a list of Char; they are distinct types:

let s: String = "hi"
let cs: [Char] = ['h', 'i']

s and cs are not interchangeable. You can’t write s[0] expecting a Char, and you can’t pass a String where [Char] is expected.

In Unicode there is no simple correspondence between “character” and “index”. An emoji can occupy several codepoints; an accented letter may have one or two representations; a grapheme can skip bytes and codepoints arbitrarily. Treating a string as a list of chars forces a decision about what counts as “a character” — and every decision is wrong for some case.

Internally, a String is a UTF-8 buffer. Its operations live in the stdlib’s string module, which makes explicit a distinction many languages paper over: bytes versus Unicode codepoints. The moment you leave ASCII they differ, and each function’s name tells you which unit it works in.

Measure "café" all four ways:

  • length(s) counts bytes, in O(1). For "café" it returns 5, not 4: the é takes two bytes in UTF-8. byte_length(s) is the same number with the unit in the name, for when the code reads better if nobody has to assume.
  • char_count(s) counts Unicode codepoints. For "café" it returns 4 — the length a reader would say aloud.
  • chars(s) decodes the buffer and hands back the codepoints as [Char]; from_chars puts them back together.
  • bytes(s) hands back the raw octets as [Byte], one per byte, splitting any multibyte codepoint into pieces; from_bytes is its inverse.

Notice that the two views have different types: [Char] is characters, [Byte] is octets, so you cannot cross them by accident — handing from_chars the result of bytes(s) does not compile, because an octet is not a character and the compiler knows it.

# examples/ch04/07_strings.kai
import core.string
import core.list

fn main() {
  let s = "café"
  println("bytes:      #{string.length(s)}")  # 5
  println("codepoints: #{string.char_count(s)}")  # 4
  println("chars:      #{list.length(string.chars(s))}")  # 4
  println("bytes list: #{list.length(string.bytes(s))}")  # 5
  println("round trip: #{string.from_bytes(string.bytes(s))}")
  println("slice(2,2):      #{string.slice(s, 2, 2)}")
  println("byte_slice(2,3): #{string.byte_slice(s, 2, 3)}")
  println("byte_slice(2,2): #{string.byte_slice(s, 2, 2)}")
}
$ kai run examples/ch04/07_strings.kai
bytes:      5
codepoints: 4
chars:      4
bytes list: 5
round trip: café
slice(2,2):      fé
byte_slice(2,3): Some(fé)
byte_slice(2,2): None

The last three lines show the two ways to take a piece out of a string, which differ in the unit:

slice(s: String, from: Int, len: Int) : String
byte_slice(s: String, from: Int, len: Int) : Option[String]

slice counts codepoints. Taking "fé" out of "café" is asking for two characters from index 2, counting from zero: slice(s, 2, 2). Overrun the length and it clamps rather than failing — slice(s, 1, 9) gives "afé" — and it can never hand you a broken string, because it does not know how to cut a character in half.

byte_slice counts bytes, which is what you need when the offsets come from somewhere else: an index_of, a parser, a protocol that measures in octets. Since any byte can land inside a character, it returns Option: byte_slice(s, 2, 3) gives Some("fé") because 2 and 5 are codepoint boundaries, and byte_slice(s, 2, 2) gives None because 4 sits in the middle of the é. If you would rather snap the offset than have it refused, that is what is_char_boundary, floor_char_boundary and ceil_char_boundary are for.

The mental rule is short: the name tells you the unit. length, byte_length, bytes and byte_slice speak bytes; char_count, chars and slice speak codepoints. Search comes in the same pairs: index_of returns a byte offset, which feeds byte_slice, and char_index_of returns a codepoint index, which feeds slice.

That length counts bytes while slice counts codepoints is not a lapse in coherence. length is O(1) and can’t break anything; a cut by byte can. Each operation keeps the unit that won’t cost you. (Graphemes like an “é” built from e plus a combining accent are yet another layer; there even codepoints fall short, but you rarely need them.)

The same care shows up in case folding. core.char ships to_upper, to_lower, is_upper and is_lower for ASCII. Its sibling core.char_unicode extends all four to the alphabets whose mapping is a uniform codepoint offset: Latin-1, Latin Extended-A, Greek and Cyrillic. Whatever falls outside that rule passes through untouched, and kaikai would rather tell you so in the module’s name than pretend to full Unicode coverage:

import core.char
import core.char_unicode
import core.list
import core.string

fn upper(s: String) : String =
  string.from_chars(list.map(string.chars(s), char_unicode.to_upper))

fn main() : Unit / Stdout {
  Stdout.print(upper("café"))
  Stdout.print(upper("привет"))
  Stdout.print(upper("omega"))
  Stdout.print(upper("ωμεγα"))
  Stdout.print(upper("ωμέγα"))
  Stdout.print(upper("☃ 42"))
  Stdout.print("#{char.to_upper('k')}")
}

upper is all it takes: decode the string to codepoints with chars, apply to_upper to each one with map, and put the string back together with from_chars. The last line reaches for core.char rather than core.char_unicode, because ASCII needs no more than that.

$ kai run examples/ch04/10_case_folding.kai
CAFÉ
ПРИВЕТ
OMEGA
ΩΜΕΓΑ
ΩΜέΓΑ
☃ 42
K

The ΩΜέΓΑ line marks the edge: ωμεγα folds whole, while in ωμέγα the έ stays down, because its uppercase form does not sit at a fixed offset. Full Unicode folding needs tables, and those do not live in the stdlib yet.

To concatenate, use ++, as in chapter 3:

let greeting = "Hello, " ++ name

For interpolation, #{...} inside a literal "...".

++ is fine for joining two or three pieces. But beware of building a large string by gluing fragments in a loop: because a String is immutable, every ++ copies the whole accumulator, which lands you in O(n²) — the classic quadratic of concatenation.

If what you have is a list of strings and a separator, it is already solved: string.join walks the list once and leaves no separator dangling at the end.

string.join(["ana", "ben", "cleo"], ", ")    # "ana, ben, cleo"

StringBuilder is for the other case: when the result is assembled from pieces that are not a uniform list. It is a text accumulator that holds the fragments as you add them and only joins them at the end, in a single pass, with build. Appending is amortized O(1), and the whole assembly is O(n).

import string_builder as sb
import core.list
import core.string

type Row = { name: String, points: Int }

fn line(r: Row) : String =
  "\n#{string.pad_right(r.name, 8, ' ')}#{r.points}"

fn report(rows: [Row]) : String {
  let total = list.foldl(rows, 0, (acc, r) => acc + r.points)
  let header = sb.append(sb.new(),
                         "#{list.length(rows)} rows, #{total} points")
  let body = list.foldl(rows, header, (b, r) => sb.append(b, line(r)))
  sb.build(body)
}
$ kai run examples/ch04/09_string_builder.kai
3 rows, 40 points
ana     12
ben     7
cleo    21

The header comes out of a separate computation and each line out of a row: different sources, and join does not cover them. The builder gathers them without recopying what it already holds. The newline goes at the front of each row so the result does not end in one.

append rides the Mutable effect — internally it writes into the builder’s fragment array — while build is pure: it only reads and joins. Notice that report declares no / Mutable in its signature even though it drives append: since the builder is born and dies inside, never escaping, kaikai masks the effect at the function boundary. The rest of the API (new, with_capacity, append_char, length, is_empty) is in kai doc string_builder.

4.5 Option and Result: the daily tools

You met these two in chapter 2:

type Option[a] = None | Some(a)
type Result[a, e] = Ok(a) | Err(e)

Now you put them to work. They are generic sum types from the stdlib that you will use constantly. Option says “there might be no value”; Result, “there is either a value or an error”.

A function that finds the first even element of a list:

fn first_even(xs: [Int]) : Option[Int] =
  match xs {
    [] -> None
    [h, ...t] -> if h % 2 == 0 { Some(h) } else { first_even(t) }
  }

And the caller has to consider both cases explicitly:

match first_even(xs) {
  Some(n) -> println("found: #{n}")
  None    -> println("no evens")
}

A function that parses an age from a string can fail in two distinct ways — and that’s exactly what Result is for:

type AgeError = NotNumeric | OutOfRange

fn parse_age(s: String) : Result[Int, AgeError] =
  match string.to_int(s) {
    None -> Err(NotNumeric)
    Some(n) ->
      if n < 0 or n > 130 { Err(OutOfRange) }
      else { Ok(n) }
  }

Result[Int, AgeError] reads as “an Int or an error of type AgeError”. The successful value is in the first parameter and the error in the second, as in Rust and most modern languages.

Four patterns you’ll see often:

  • Chain a failure with !. If you have an expression that returns Result[A, E] and you want “if it fails, propagate the error; otherwise continue with the value”, you write expr!, as in §2.3.
  • A default with ??. o ?? d is whatever o carries when it is Some, and d when it is None. The right side runs only in the None case, so first_even(xs) ?? compute() computes nothing when it found something. It is for Option; a Result goes in as ok(r) ?? d.
  • Higher-order functions: option.map, option.and_then, result.map_err. They arrive in chapter 6, and so do the pipes, which run over Option and Result just as over a list: Some(2) | double is Some(4).
  • Convert between the two: option.ok_or(error) takes an Option[a] and an error of type e and returns a Result[a, e]. Useful when the information lost by None isn’t enough.

Option and Result are sum types like any other. I pulled them out of chapter 5 because their role in day-to-day design is central — you’ll use them before you start declaring your own sum types.

Both types at work: a search that may find nothing, and a validation that explains why it failed:

# examples/ch04/04_option_result.kai
type AgeError = NotNumeric | OutOfRange

fn first_even(xs: [Int]) : Option[Int] =
  match xs {
    [] -> None
    [h, ...t] -> if h % 2 == 0 { Some(h) } else { first_even(t) }
  }

fn parse_age(s: String) : Result[Int, AgeError] =
  match string.to_int(s) {
    None -> Err(NotNumeric)
    Some(n) ->
      if n < 0 or n > 130 {
        Err(OutOfRange)
      } else {
        Ok(n)
      }
  }

fn describe_age(s: String) : String =
  match parse_age(s) {
    Ok(n) -> "valid age: #{n}"
    Err(NotNumeric) -> "not a number"
    Err(OutOfRange) -> "out of range"
  }

fn main() {
  let xs = [1, 3, 5, 6, 7]
  match first_even(xs) {
    Some(n) -> println("first even: #{n}")
    None -> println("no evens")
  }

  println(describe_age("42"))
  println(describe_age("hello"))
  println(describe_age("999"))
}
$ kai run examples/ch04/04_option_result.kai
first even: 6
valid age: 42
not a number
out of range

4.6 Tuples

A tuple is a positional aggregate: like a record, but without field names. The syntax is parentheses with elements:

let point2d = (3, 4)
let trio    = ("Ada", 30, true)

The type is written the same way: (Int, Int), (String, Int, Bool).

kaikai admits tuples of arity 2 to 4. There are no 1-element tuples — a single parenthesis, (e), is grouping, not a tuple. And (a, b, c, d, e) is a parse error.

The bound is there because long tuples are unreadable. If you’re hitting 5 elements, almost always what you wanted was a record with named fields.

To take a tuple apart, destructuring:

fn divmod(a: Int, b: Int) : (Int, Int) = (a / b, a % b)

fn main() {
  let (quotient, remainder) = divmod(17, 5)
  println("17/5 = #{quotient}, remainder #{remainder}")
}

Internally, tuples are sugar over three records from the stdlib: Pair[A, B] for arity 2, Triple[A, B, C] for 3, Quad[A, B, C, D] for 4. The declaration

let p = (1, 2)

is exactly equivalent to

let p = Pair { fst: 1, snd: 2 }

So when you see Pair[Int, String] in a stdlib signature, you know it’s (Int, String) and that let (a, b) = p destructures it.

A function that returns two values, and a caller that splits them in the let:

# examples/ch04/05_tuples.kai
fn divmod(a: Int, b: Int) : (Int, Int) = (a / b, a % b)

fn main() {
  let (quotient, remainder) = divmod(17, 5)
  println("17 / 5 = #{quotient}, remainder = #{remainder}")

  # A 3-tuple
  let point3d = (1, 2, 3)
  let (x, y, z) = point3d
  println("(#{x}, #{y}, #{z})")
}
$ kai run examples/ch04/05_tuples.kai
17 / 5 = 3, remainder = 2
(1, 2, 3)

Tuple or record?

When in doubt, use a record. Tuples are convenient for cases where names don’t add — the result of divmod, where “the first value is the quotient and the second the remainder” is information the reader already gets from the function name. Or when the aggregate lives one step:

xs |> map((e) => (e.name, e.age))

But as soon as the same aggregate appears more than once, or crosses a module boundary, or its shape is something the reader can’t deduce, prefer a record. An Employee is much easier to read than a (String, Int, Bool, String, Int).

4.7 Hash maps and sets

Everything you’ve used so far is immutable: a new record doesn’t mutate the old one, a list with one more element is a new list. For most code that’s exactly what you want. But sometimes you need a real associative table — insert and look up by key in near-constant time — and building a fresh record on every insertion won’t cut it. For that the stdlib ships two mutable structures: HashMap[k, v], which maps keys to values, and HashSet[a], a set with no duplicates.

That they’re mutable shows up in the effect row: the operations that write (put, add, remove) yield Mutable. If you come from Python or Java, a dictionary that changes in place feels obvious; what’s new here is that the language says so in the type whenever someone outside can notice. The rule is the one from the StringBuilder in §4.4: if the function creates the table and fills it itself, nobody else sees the mutation, and kaikai masks the effect at the function’s edge, even when the function returns the filled table. A function that modifies a table it received as a parameter does carry / Mutable in its signature, and the compiler makes you declare it. Immutability is still the default; visible mutation is marked where it happens.

Key access uses indexing, m[key], which returns an Option — Some(v) if the key is present, None if it isn’t — so a missing key never blows up in your face:

import collections.hashmap as hashmap

fn count(m: hashmap.HashMap[String, Int], w: String) : Unit / Mutable {
  let current = match m[w] {
    Some(n) -> n
    None    -> 0
  }
  hashmap.put(m, w, current + 1)
}

count writes to a table it doesn’t own, so it declares Mutable.

The match on the Option has a shortcut: unwrap_or(m[w], 0) does the same in one expression, and it is what the example uses.

A full example: count how often each word in a list appears, first with a HashMap, and along the way use a HashSet to count how many distinct words there are.

import collections.hashmap as hashmap
import collections.hashset as hashset

fn word_frequencies(words: [String]) : hashmap.HashMap[String, Int] {
  let m = hashmap.empty()
  words |! hashmap.put(m, ., unwrap_or(m[.], 0) + 1)
  m
}

fn main() : Unit / Stdout {
  let text = ["sun", "sea", "sun", "wind", "sea", "sun"]
  let m = word_frequencies(text)
  match m["sun"] {
    Some(n) -> Stdout.print("sun appears #{n} times")
    None    -> Stdout.print("sun does not appear")
  }
  Stdout.print("distinct words: #{hashmap.size(m)}")

  # A HashSet drops duplicates on insertion.
  let seen = hashset.empty()
  text |! hashset.add(seen, .)
  Stdout.print("unique via set: #{hashset.size(seen)}")
}
$ kai run examples/ch04/08_maps.kai
sun appears 3 times
distinct words: 3
unique via set: 3

Neither word_frequencies nor main declares Mutable: each structure is born inside the function that fills it, and the caller only gets the result.

hashmap.put inserts or replaces in place; hashmap.get is the named form of m[key]; size, keys, values, remove and contains round out the day-to-day. The HashSet is the valueless face of the same idea: add, contains, size, plus the set operations union, intersection and difference. The full list, with signatures, comes out of kai doc collections/hashmap and kai doc collections/hashset (ch. 16 covers kai doc).

One note on order: neither the HashMap nor the HashSet promises a traversal order. keys, values and to_pairs hand you the elements in the internal bucket order, which is not insertion order. If you need order, sort at the end or reach for the stdlib’s ordered structure (Map, built on an AVL tree).

Map also compares by content: two maps holding the same pairs are equal even when they were built by inserting in a different order. That makes it the right structure when the result leaves the function and something downstream will compare it against an expectation. The bridge between the two families lives in collections/convert: convert.to_map(h) freezes a HashMap once the fast build is done, and convert.to_hashmap(m) goes the other way.

Exercises

4.1. Define a record Book with fields title, author and pages. Write a function fn short(b: Book) : Bool that returns true if the book has fewer than 200 pages. Build two books and try the function.

4.2. Write fn maximum(xs: [Int]) : Option[Int] returning the largest element of the list, or None if the list is empty. Use recursion and match.

4.3. Rewrite fn parse_age from §4.5 so it distinguishes three errors: not numeric, negative age, age > 130. Use a sum type with three constructors and a Result.

4.4. Define a function fn split(xs: [Int]) : ([Int], [Int]) returning a tuple with the evens and odds of xs, each in original order. Why a tuple and not two return values? And why a tuple and not a record?

4.5. Given a [Point] (with Point = { x: Int, y: Int }), write fn center(ps: [Point]) : Option[Point] returning the average of coordinates, or None if the list is empty. Hint: you’ll need two passes or an accumulator, and int_to_real to average — but note the final result has to be a Point with Int fields, so you’ll also need real_to_int (or settle for the integer part).

4.6. On paper, without writing code, draw what happens in memory when you run these three lines:

let xs = [1, 2, 3]
let ys = [0, ...xs]
let zs = [99, ...xs]

How many lists were created? How many elements were copied? Are there cells that xs, ys, zs share? The answer helps you understand why immutability isn’t expensive when the structures are linked.

← Back to contents