Step 6. Collections and iterators

Why#

Three collections cover the vast majority of tasks: List<T> (an ordered list), Map<K, V> (a dictionary) and Set<T> (a set of unique values). Map and Set iterate in insertion order, so the output is deterministic - this matters for tests and reproducible logs.

Processing collections is a pipeline "filter -> transform -> collect". Pipelines are lazy: an iter<T> computes nothing until you ask for the result (toList, fold, for). A long pipeline therefore creates no intermediate lists.

List, map, set#

fn main() io {
  var xs: List<i32> = [5, 3, 8]
  xs.push(1)
  xs.sort()
  print("{xs} first={xs.first() ?? -1} last={xs.last() ?? -1}")
  print("{xs.map(x => x * 10)} {xs.filter(x => x > 3)} sum={xs.fold(0, (a, x) => a + x)}")
  print("{xs.contains(8)} {xs.any(x => x > 7)} {xs.all(x => x > 1)} {xs.count(x => x % 2 == 1)}")

  var stock: Map<str, i32> = {"apple": 3, "pear": 0}  // Map<K, V>: literal {k: v}
  stock["plum"] = 7  // assignment by key inserts or replaces
  print("{stock.get("apple") ?? 0} {stock.get("kiwi") ?? -1} {stock.len()}")
  stock.remove("pear")
  for (k, v) in stock.iter().sortBy(p => p.0) { print("{k}={v}") }

  var seen: Set<str> = Set.new()
  print("{seen.insert("a")} {seen.insert("a")} {seen.contains("a")} {seen.len()}")
}

[1, 3, 5, 8] first=1 last=8
[10, 30, 50, 80] [5, 8] sum=17
true true false 3
3 -1 3
apple=3
plum=7
true false true 1

Walkthrough#

• xs.push(1), xs.sort() change the list in place and therefore need var. map, filter, fold return a new value.
• xs.first() returns T? - an empty list has no first element, and ?? -1 provides a default. The same goes for get of a list and a map: going out of bounds through get is not a panic but none.
• {"apple": 3} is a map literal, {:} an empty map (empty {} is a block). stock["plum"] = 7 inserts or replaces.
• Set.insert returns true when the element is new.
• Iterating a map yields (key, value) pairs; sortBy orders them.

Lazy iterators and queries#

fn main() io {
  let nums = 1..=10
  let evens = nums.iter().filter(n => n % 2 == 0).map(n => n * n)  // a lazy chain: nothing computed yet
  print("{evens.toList()}")  // toList runs the computation

  let words = ["pear", "fig", "banana", "kiwi", "apple"]
  let q = from w in words where w.len() > 3 order by w.len() desc, w select "{w}:{w.len()}"  // a query is the same pipeline written as an expression
  print("{q.toList()}")

  let pairs = words.iter().enumerate().skip(1).take(2).toList()
  print("{pairs}")
  let total = (1..=100).iter().takeWhile(n => n * n < 200).fold(0, (a, n) => a + n)
  print("{total}")
  print("{words.iter().map(w => w.len()).max() ?? 0}")
  let byLen = from w in words group by w.len() into g select (g.key, g.count())
  print("{byLen.toList()}")
}

[4, 16, 36, 64, 100]
["banana:6", "apple:5", "kiwi:4", "pear:4"]
[(1, "fig"), (2, "banana")]
105
6
[(4, 2), (3, 1), (6, 1), (5, 1)]

• 1..=10 is a range; .iter() turns a collection or a range into a lazy iter<T>.
• filter, map, skip, take, enumerate, takeWhile return a new iterator; the computation is started by toList(), fold, count, max, for.
• from w in words where … order by … select … is a query expression: the same thing, but it reads like SQL. For in-memory collections it is a lazy iterator; for ORM tables (a step in the tour) the same syntax compiles to SQL.
• group by … into g select (g.key, g.count()) groups; the groups come in the order of the first appearance of a key.

Common mistakes#

Calling a nonexistent method - unknown-method (in OxL the length of a list is len(), not length()):

fn main() io {
  let xs = [1, 2, 3]
  print("{xs.length()}")
}

unknown-method

The element type is checked strictly: you cannot put a string into a List<i32> - type-mismatch:

fn main() io {
  var xs: List<i32> = [1, 2]
  xs.push("three")
}

type-mismatch

Remember#

• List, Map, Set keep insertion order; lookups return T?.
• iter pipelines are lazy; you must demand the result.
• A from … select query is a convenient notation for the same pipeline.

Next: ownership and borrowing.