Lists and maps

List and map literals, built-in methods, reference semantics, and how to build an empty collection.

vlatest

List<T> and Map<K, V> are built into the compiler, not the standard library. They are always parameterised, there is no untyped collection, and they use reference semantics.

List literals

fn main() {
    let xs = [1, 2, 3]
    let strings = ["a", "b"]

    println(len(xs))           // 3
    println(xs[0])             // 1
    for (x in xs) {
        print("{x} ")
    }
    println("")
}

The element type is inferred from the elements.

Building an empty collection

An empty literal has no elements to infer the element type from, and there is no List<T>() or Map<K, V>() constructor:

fn main() {
    // let xs = []                    // cannot infer the element type
    // let ys = List<int>()           // E0410: unknown generic function `List`
    // let zs = Map<string, int>()    // same
}

Collections are always parameterised, so an empty collection needs its type supplied some other way. You have three working options.

1. Start from a non-empty literal and mutate it.

fn main() {
    let xs = [0]
    xs.remove(0)
    println("len {len(xs)}")     // 0
}

2. Take a prototype value from a function parameter.

fn pick(items: List<int>, index: int) -> int? {
    if (index < 0) {
        return none
    }
    if (index >= len(items)) {
        return none
    }
    return items[index]
}

3. Use a standard-library collection, which takes a prototype value.

This is the idiomatic answer for stacks, queues, sets and so on, see Collections in the standard library:

import { Stack } from std.collections.stack

fn main() {
    let s = Stack<int>(0)      // 0 is a prototype, not a starting element
    println("size {s.size()}") // 0
    s.push(1)
    match (s.pop()) {
        case some(v) -> { println("popped {v}") }
        case none -> { println("empty") }
    }
}

List methods

Method Signature Returns
push push(value: T) void
pop pop() T
remove remove(index: int) T
insert insert(index: int, value: T) void
sort sort() void

Note that pop and remove return the element, not an optional. There is no T? to match on, and no bounds check is reported by the type checker, guard the index yourself, or use a Stack / Queue from the standard library, whose pop does return T?.

fn main() {
    let xs = [5, 1, 3]
    xs.push(2)
    xs.insert(0, 0)

    for (x in xs) {
        print("{x} ")          // 0 5 1 3 2
    }
    println("")

    xs.sort()
    for (x in xs) {
        print("{x} ")          // 0 1 2 3 5
    }
    println("")

    let removed = xs.remove(0)
    println("removed {removed} first is now {xs[0]}")

    let last = xs.pop()
    println("popped {last}, len {len(xs)}")
}

sort is available only when the element type is sortable, numbers, char, string and bool. It sorts in place and returns nothing.

Reference semantics

A list bound to two names is one list:

fn main() {
    let a = [1, 2]
    let b = a
    b.push(3)
    println(len(a))            // 3
}

A function that takes a List<T> can change what the caller sees:

fn pushTwice(xs: List<int>, v: int) -> void {
    xs.push(v)
    xs.push(v)
}

fn main() {
    let xs = [1]
    pushTwice(xs, 9)
    println(len(xs))           // 3
}

Map literals and methods

fn main() {
    let m = {"a": 1, "b": 2}

    println(m["a"])            // 1
    println(len(m))            // 2
    println(m.has("a"))        // true

    m["c"] = 3
    for (k in m.keys()) {
        print("{k} ")
    }
    println("")
    for (v in m.values()) {
        print("{v} ")
    }
    println("")
}
Method Signature Returns
has has(key: K) bool
get get(key: K) V?
remove remove(key: K) V?
keys keys() List<K>
values values() List<V>

get and remove are the two that return optionals, so they are how you test for absence without an exception:

fn main() {
    let m = {"a": 1}
    match (m.get("a")) {
        case some(v) -> { println("a = {v}") }
        case none -> { println("no key a") }
    }
    match (m.remove("a")) {
        case some(v) -> { println("removed {v}") }
        case none -> { println("nothing to remove") }
    }
    println(len(m))            // 0
}

Indexing a missing key is not the way to test for absence.

Generics and invariance

List<T> is invariant: a List<int> is not a List<float>, even though int converts to float. A function must be written for exactly the element type it receives.

fn total(xs: List<int>) -> int {
    var sum = 0
    for (x in xs) {
        sum += x
    }
    return sum
}

fn main() {
    println(total([1, 2, 3]))   // 6
    // println(total([1.0, 2.0]))   // error: `List<int>` expected
}

Convert element by element rather than casting the list:

fn toInts(xs: List<float>) -> List<int> {
    if (len(xs) == 0) {
        return [0]             // empty literals cannot be typed
    }
    let out = [xs[0] as int]
    for (i in 1..len(xs)) {
        out.push(xs[i] as int)
    }
    return out
}

Heterogeneous data

A list of a common interface type works, but each element needs an explicit cast the literal takes its element type from the first element, and there is no upcast:

interface Animal {
    fn speak() -> string
}

class Dog implements Animal {
    fn speak() -> string { return "woof" }
}

class Cat implements Animal {
    fn speak() -> string { return "meow" }
}

fn main() {
    // let bad = [Dog(), Cat()]                  // error: expected `Dog`, found `Cat`
    // let bad2: List<Animal> = [Dog(), Cat()]   // error: found `List<Dog>`
    let animals = [Dog() as Animal, Cat() as Animal]
    for (a in animals) {
        println(a.speak())     // woof
                               // meow
    }
}

Nesting

Lists and maps nest freely:

fn main() {
    let table = {"one": [1, 2], "two": [3, 4]}
    println(table["one"][0])    // 1
}

Custom iteration

Any type can be iterated by implementing the two prelude interfaces, Iterable<T> and Iterator<T>. for calls iterator() and then next() until it returns none.

class Countdown implements Iterable<int> {
    var start: int

    constructor(start: int) {
        this.start = start
    }

    fn iterator() -> Iterator<int> {
        return Counter(this.start)
    }
}

class Counter implements Iterator<int> {
    var n: int

    constructor(n: int) {
        this.n = n
    }

    fn next() -> int? {
        if (this.n <= 0) {
            return none
        }
        this.n -= 1
        return this.n
    }
}

fn main() {
    for (v in Countdown(4)) {
        print("{v} ")      // 3 2 1 0
    }
    println("")
}

Counter is declared after Countdown here, but only because for is what needs it, the resolver still requires the declaration order you write.

Next steps