Lists and maps
List and map literals, built-in methods, reference semantics, and how to build an empty collection.
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
- Collections in the standard library: sets, deques, stacks, queues, ordered maps, priority queues.
- Generics and interfaces
