Skip to content

Collections and iteration

Every collection reports membership, and x in c asks it (spec §8 Membership; tour: Collections): a set, a map (a key), a range, a list, a vector, bytes and a string. Write name in reserved, not List.contains(reserved, name) or Contains.contains(reserved, name), for a Bool test:

if name in reserved then
    Err("${name} is reserved")
else
    Ok(name)
end

not Iter.any_match(reserved, fn r -> r == name), which spells out the comparison in makes. Keep Iter.any_match for a predicate other than ==, and Iter.contains for a lazy pipeline, which has no Contains impl. A predicate that only tests membership needs no lambda: Iter.reject(&(&1 in seen)). Name the function (Set.contains) only where a function value is wanted. A List, Vector, Bytes or Iter lookup is a linear scan, so a value looked up repeatedly belongs in a Set: convert once with Iter.to_set and test that.

A bounds check is a range membership test too: not square in 1..=64, not square < 1 or square > 64. The range states the valid values once, and its .. or ..= says whether the upper bound is one of them.

When code asks what stands at positions of a grid, read the grid once into a Set of the positions that hold something, or a Map from each position to what is there (std::sets, std::maps; tour: Collections), and ask that. A position off the grid is absent, so a neighbour needs no bounds check and no Vector.get(...)! pair:

flowers =
    garden
    |> Iter.with_index()
    |> Iter.flat_map(fn (row, line) ->
        line
        |> Iter.with_index()
        |> Iter.filter(fn (_column, square) -> square == "*")
        |> Iter.map(fn (column, _square) -> (row, column))
    end)
    |> Iter.to_set()

count = Iter.count_by(neighbours, fn (dr, dc) -> (row + dr, column + dc) in flowers)

Keep a Vector<Vector<T>> read with Vector.get when the code reads whole rows and columns by index, as a matrix does.

33. Reach for a named fold before Iter.reduce

Section titled “33. Reach for a named fold before Iter.reduce”

std::iter names the common folds (tour: Iteration & Loops). A fold that starts from the empty sum and adds each element is Iter.sum:

total = prices |> Iter.map(.cents) |> Iter.sum()

not Iter.reduce(0, fn total, n -> total + n), which spells out the starting value and the step the type’s Summable and Add impls already name. A fold that multiplies from 1 is Iter.product for the same reason, and a fold that multiplies one value by itself is Int.pow or Decimal.pow: Int.pow(10, zeros), not Iter.reduce(1..=zeros, 1, fn n, _ -> n * 10). A fold that sums and counts to divide is Iter.mean, which reads the source once and rounds once.

A fold whose every intermediate state is wanted is Iter.scan, and a map that threads a state from one element to the next is Iter.map_reduce:

balances = deposits |> Iter.scan(opening, fn balance, amount -> balance + amount)

(_width, rows) =
    lines
    |> Iter.reverse()
    |> Iter.map_reduce(0, fn width, line ->
        width = Int.max(width, String.length(line))
        (width, String.pad_end(line, width))
    end)

not an Iter.reduce whose accumulator is a (state, list) pair that conses each result and is reversed afterwards. Use scan when the outputs are the states themselves, and it stays lazy, so it can run over an unbounded source under a take. Use map_reduce when each element has its own output and the state only carries what the next one needs.

A fold whose step can fail is Iter.try_reduce(rolls, Game.new(), Game.roll), which stops at the first Err, not an Iter.reduce with ? on a Result accumulator, which visits every element and whose ? leaves only the lambda.

Keep Iter.reduce when only the final state is wanted and the fold does more than add (total + n * weight), starts from another value, or breaks early. Its starting value is the positional argument before the callback, unnamed: Iter.reduce(orders, 0, fn total, o -> total + o.cents). A named function is passed itself, after the starting value:

total = Iter.reduce(orders, 0, add_order)

not Iter.reduce(orders, 0, fn total, o -> add_order(total, o)), a lambda that only passes its parameters on. A capture is passed the same way: Iter.reduce(counts, {}, &Map.merge_with(&1, &2, Int.add)). Iter.loop takes a named step the same way, Iter.loop(start, step).

34. Number elements with Iter.with_index, not a counter in the state

Section titled “34. Number elements with Iter.with_index, not a counter in the state”

When a step needs each element’s position, pair the elements with it (Iter.with_index) and take the pair apart in the lambda, rather than carrying a counter in an Iter.reduce state or a recursion’s parameters:

fn checksum(digits: List<Int>) -> Int
    digits
    |> Iter.reverse()
    |> Iter.with_index()
    |> Iter.map(fn (i, d) -> if i % 2 == 1 then double(d) else d)
    |> Iter.sum()
end

not an Iter.reduce whose state is (total, index), or a parity flag flipped at each step. The position comes from the element, and what remains is a plain map and a named fold (§33). The index counts from 0.

35. Choose between recursion, Iter.loop and Iter.iterate

Section titled “35. Choose between recursion, Iter.loop and Iter.iterate”

Each fits a different shape of repetition:

  • Iter.iterate(start, next) for a sequence where each value comes from the one before, of which you want some or all values. The pipeline after it says how much: take, take_while, count, find.
  • Iter.loop (spec §13 loop; tour: Iteration & Loops) for a state that changes until a condition ends it with break, when only the final state is wanted.
  • Recursion when the data is recursive (a tree, a grammar, nested lists), when a step can fail and ? should end the whole walk, and for a search that backs out of dead ends. A recursive call in tail position runs in constant stack space (spec §7 Tail-call optimization); a call that is not grows the stack at each level.
// a sequence: iterate, then cut it
fn steps(number: Int) -> Int
    Iter.iterate(number, next)
    |> Iter.take_while(&(&1 != 1))
    |> Iter.count()
end

// a state until a condition: loop
fn first_power_above(limit: Int) -> Int
    Iter.loop(1, fn n ->
        if n > limit then break n
        n * 2
    end)
end

A tail-recursive counter does what the first does, and spells out the count the pipeline names. Prefer a pipeline over the collection when the loop only walks a collection: Iter.map, a named fold (§33) or Iter.find.

36. Build a list newest first and reverse it once

Section titled “36. Build a list newest first and reverse it once”

A List is linked: [x, ..rest] puts x in front in constant time, and [..rest, x] copies rest to put x at its end (spec §4 List). A recursion or loop that grows a list one element per step conses, and reverses the list once when it is done:

// yes: each step conses, and the finished trail is reversed once
fn trail(at: Point, seen: List<Point>) -> List<Point>
    case next_step(at)
        Some(step) -> trail(step, [at, ..seen])
        None       -> Iter.reverse([at, ..seen])
    end
end

// no: each step copies the trail to add one point
fn trail(at: Point, seen: List<Point>) -> List<Point>
    case next_step(at)
        Some(step) -> trail(step, [..seen, at])
        None       -> [..seen, at]
    end
end

Say in the parameter’s doc comment that it is held newest first. When each element of an input gives one output, Iter.map or Iter.map_reduce builds the list in order and needs neither (§33).

37. Sort by several keys with one tuple key

Section titled “37. Sort by several keys with one tuple key”

Tuples compare element by element (spec §5 Ordering requires a declared Comparable; tour: Interfaces & Dispatch), so a sort by several keys is one Iter.sort_by whose key is a tuple of them, most significant first. Wrap a key in Reverse.of (std::reverse) to sort it descending; it works for any Comparable key, and reads as intent where negating a number reads as arithmetic:

// most points first, then by name
table = Iter.sort_by(standings, fn s -> (Reverse.of(s.points), s.team))

Don’t chain stable sorts, |> Iter.sort_by(.team) and then |> Iter.sort_by(Direction.Descending, .points): the reader has to know the sort is stable and read the keys bottom up. To sort a whole list descending, pass Direction.Descending (std::comparable). Iter.sort_with and Ordering.chain remain for a comparator that is not a key, such as one that compares by a function of both values.