Collections

Three owning containers, one view type, and a standard library that works on the view. That is the whole collection story, and it fits in one program.

import std.lists
import std.strings

fn is_even(x: i32) -> bool { return x % 2 == 0 }
fn double(x: i32) -> i32 { return x * 2 }
fn add(acc: i64, x: i32) -> i64 { return acc + x as i64 }

fn main() {
    // List(T): a growable, owned sequence
    var xs = List(i32).new()
    for i in 1..8 { let v = i as i32; xs.append(v * v) }
    xs.insert(0, 0)
    let last = xs.pop().?
    println("{} items, last was {}, first {}", .{xs.len, last, xs[0]})
    xs.sort()
    xs.reverse()
    println("{} {} contains 16: {}", .{xs[0], xs[1], xs[..].contains(16)})

    // slices view a range without copying
    let top = xs[0..3]
    var sum: i32 = 0
    for v in top { sum += v }
    println("top three sum to {}", .{sum})

    // std.lists: the usual higher-order helpers, over any slice
    let evens = lists.filter(i32, xs[..], is_even)
    let doubled = lists.map(i32, i32, evens[..], double)
    let total = lists.fold(i32, i64, xs[..], 0, add)
    println("{} evens, doubled: {} {} ..., total {}", .{evens.len, doubled[0], doubled[1], total})
    println("max {} min {}", .{lists.max(i32, xs[..]) orelse 0, lists.min(i32, xs[..]) orelse 0})

    // String: owned text; []u8: a view of bytes (a literal is one)
    var s = String.from("base")
    s.append(" camp")
    s.append_char('!')
    let upper = strings.to_upper(s[..])
    println("{} / {} / {} bytes", .{s, upper, s.len})
    for part, i in s[..].split(" ") { println("  part {}: {}", .{i, part}) }
    println("{} {} {}", .{s[..].starts_with("base"), s[..].find("camp") orelse 0, s[..].trim().len})
    let parts = ["one", "two", "three"]
    println("{}", .{strings.join(parts[..], ", ")})
    println("{}", .{strings.replace("a-b-c", "-", "+")})

    // numbers from text
    let n = "42".parse_int(i32) catch 0
    let f = "2.5".parse_float() catch 0.0
    println("{} {}", .{n + 1, f * 2.0})

    // Map(K, V): keys are integers, bools, chars, text or Strings
    var stock = Map(String, u32).new()
    stock.put(String.from("rope"), 2)
    stock.put(String.from("ice screw"), 12)
    stock.put(String.from("rope"), 3)
    println("{} kinds; rope: {}; tent: {}", .{stock.len, stock["rope"] orelse 0, stock["tent"] orelse 0})
    if stock.contains("ice screw") { println("we have screws", .{}) }
    _ = stock.remove("rope")
    var names = stock.keys()
    println("{} left: {}", .{stock.len, names[0]})

    // arrays: fixed size, a value; copying one copies the elements
    var grid = [[0, 0, 0], [0, 0, 0]]
    grid[1][2] = 7
    let copy = grid
    grid[1][2] = 9
    println("{} {}", .{copy[1][2], grid[1][2]})
}

7 items, last was 49, first 0
36 25 contains 16: true
top three sum to 77
4 evens, doubled: 72 32 ..., total 91
max 36 min 0
base camp! / BASE CAMP! / 10 bytes
  part 0: base
  part 1: camp!
true 5 10
one, two, three
a+b+c
43 5.0
2 kinds; rope: 3; tent: 0
we have screws
1 left: ice screw
7 9

List(T)#

A growable sequence that owns its elements. List(i32).new() is empty; with_capacity(n) reserves; List(u8).from("abc") copies from a slice. append, insert(i, v), pop() -> ?T, remove(i), swap_remove(i), extend(slice), clear, last() -> ?T, first(), len, is_empty. Index with xs[i], which panics past the end (chapter 15 says when the compiler can prove it cannot). A List is a slice wherever a slice is wanted, so every slice method below is a List method too, and xs[..] names the whole thing explicitly when you need to.

Appending an owning value moves it in (kept.append(w.clone()) in the ownership chapter); reading one out is &xs[i], a borrow, because moving an element out would leave a hole. xs.pop() is the way to take the last one.

Slices#

[]T is a pointer and a length: len, contains, index_of, sort (for ordered element types), reverse, fill, copy_from, to_owned (a fresh List), is_empty. []mut T is the same view with permission to write through it; a var array or list gives one, let gives the read-only kind. Ranges cut sub-slices, xs[1..3], xs[2..], xs[..2].

std.lists adds what a functional style wants, generic over the element type: filter, map, fold, any, all, find, position, min, max, sum, zip, dedup, take, drop. They take a function value as the last argument; a plain function's name (is_even) is one, and so is a closure |[] x: i32| -> bool { x > 2 } with its captures listed in the brackets.

String and []u8#

String owns text: String.new(), String.from(slice), append(slice), append_char(c) (a code point, UTF-8 encoded), push_byte(b), clear, pop, len. A string literal is a []u8, and every []u8 operation is available on a String through s[..]: split(sep), lines(), trim(), find(needle) -> ?usize, starts_with, ends_with, eq_ignore_case, parse_int(T), parse_float(), to_string().

The pieces split and lines return are views into the original bytes: free to make, valid while the original lives. std.strings has join, replace, repeat, pad_left, to_upper, split_whitespace, split_once and the rest; std.text is for the cases where a character is not a byte (char_count, chars, width, to_upper for non-ASCII letters).

format("{}", .{...}) builds a String; it is println without the printing.

Map(K, V)#

A hash map. Keys may be integers, bool, char, text ([]u8 or String) or any struct that derives Hash and Eq. put(k, v) inserts or replaces (and takes ownership of both), get(k) -> ?V, m[k] is the same lookup, contains, remove(k) -> ?V, keys() and values() collect into Lists, len, clear. for k in m walks the keys and for (k, v) in m the entries; the order is the map's own, not insertion order, so sort the keys when the order shows.

A Map(String, V) is looked up with a []u8: the key you store is owned, the key you search with is a view, which is what stock["rope"] above relies on.

Arrays#

[N]T has a length in its type and is a value: assigning it copies every element, which is what you want for a small fixed table and not for anything large. var grid = [[0, 0, 0], [0, 0, 0]] is [2][3]i64, indexed grid[r][c]. An array coerces to a slice, so anything that takes []T takes arr[..].

Choosing#

• A sequence that grows: List.
• A function parameter: a slice, always, unless the function keeps the data (then own List).
• Text you build: String; text you look at: []u8.
• Lookup by key: Map.
• A fixed handful of things known at compile time: an array.

Next: a project: the calculator.

Exercises#

The compiler grades these: nx topo 9 writes them into a directory, nx topo check runs them. Or do them here: the code is editable, Run runs it with the compiler in the page (it loads on the first run and never sends your code anywhere), Check grades it as nx topo check would, and Reset puts the exercise back. Ctrl+Enter runs.

fn main() {
    var counts = Map([]u8, u32).new()
    for w in ["col", "ridge", "col", "summit", "col"] {
        let n = counts.get(w) ??? 0
        counts.???(w, n + 1)
    }
    println("{} {} {}", .{counts.len, counts["col"].?, counts.get("summit") orelse 0})
}

3 3 1

fn main() {
    var counts = Map([]u8, u32).new()
    for w in ["col", "ridge", "col", "summit", "col"] {
        let n = counts.get(w) orelse 0
        counts.put(w, n + 1)
    }
    println("{} {} {}", .{counts.len, counts["col"].?, counts.get("summit") orelse 0})
}

fn unique(xs: []i32) -> List(i32) {
    ???
}

fn main() {
    let xs: [7]i32 = [3, 1, 3, 2, 1, 5, 3]
    let u = unique(xs[..])
    println("{} {} {} {} {}", .{u.len, u[0], u[1], u[2], u[3]})
}

test "keeps the first of each" {
    let xs: [7]i32 = [3, 1, 3, 2, 1, 5, 3]
    let u = unique(xs[..])
    expect_eq(u.len, 4)
    expect_eq(u[0], 3)
    expect_eq(u[1], 1)
    expect_eq(u[3], 5)
}

test "empty stays empty" {
    let none = List(i32).new()
    expect_eq(unique(none[..]).len, 0)
}

4 3 1 2 5

fn unique(xs: []i32) -> List(i32) {
    var out = List(i32).new()
    for x in xs {
        if !out[..].contains(x) { out.append(x) }
    }
    return out
}

fn main() {
    let xs: [7]i32 = [3, 1, 3, 2, 1, 5, 3]
    let u = unique(xs[..])
    println("{} {} {} {} {}", .{u.len, u[0], u[1], u[2], u[3]})
}

test "keeps the first of each" {
    let xs: [7]i32 = [3, 1, 3, 2, 1, 5, 3]
    let u = unique(xs[..])
    expect_eq(u.len, 4)
    expect_eq(u[0], 3)
    expect_eq(u[1], 1)
    expect_eq(u[3], 5)
}

test "empty stays empty" {
    let none = List(i32).new()
    expect_eq(unique(none[..]).len, 0)
}