19. Higher-Order Combinators

Chapters 17 and 18 gave you function values and closures. This chapter puts them to work with three classic list combinators — map, filter, and fold — plus compose, all from the opt-in collections/iter module.

Unlike List and HashMap, these are not always in scope: you bring them in with a use.

use <collections/iter>

collections/iter is the first Sushi module written in Sushi itself — the combinators are ordinary generic functions that compile alongside your program. Nothing is generated unless you actually call one, so an unused use costs nothing.

map — transform every element

map(xs, f) applies f to each element of a List<T> and collects the results into a new List<U>:

use <collections/iter>

fn main() i32:
    let i32 crew = 4
    let List<i32> ages = List.new()
    ages.push(30)
    ages.push(42)
    ages.push(200)
    # Everyone gains `crew` years while stuck on the Heart of Gold.
    let List<i32> older = map(ages, |i32 a| a + crew).realise(List.new())
    println(older.get(1).realise(-1))
    return Result.Ok(0)

Output:

46

The lambda |i32 a| a + crew captures the outer local crew (Chapter 18) — combinators and closures work together with no special ceremony. Note the call is map(ages, ...), not ages.map(...): these are free functions, so the list is the first argument.

filter — keep the ones that match

filter(xs, pred) keeps exactly the elements for which pred returns true:

use <collections/iter>

fn main() i32:
    let i32 minimum = 42
    let List<i32> readings = List.new()
    readings.push(10)
    readings.push(42)
    readings.push(99)
    readings.push(7)
    # Keep only the improbability readings that clear the threshold.
    let List<i32> high = filter(readings, |i32 r| r >= minimum).realise(List.new())
    println(high.len())
    return Result.Ok(0)

Output:

2

Two of the four readings (42 and 99) clear the threshold, so the filtered list has length 2.

fold — collapse a list to a single value

fold(xs, init, f) threads an accumulator through the list left to right, starting from init:

use <collections/iter>

fn main() i32:
    let List<i32> bill = List.new()
    bill.push(6)
    bill.push(6)
    bill.push(30)
    # Sum the tab at Milliways, starting from a base cover charge of 0.
    let i32 total = fold(bill, 0, |i32 acc, i32 item| acc + item).realise(-1)
    println(total)
    return Result.Ok(0)

Output:

42

Each step computes acc + item; starting from 0, the tab at Milliways comes to 6 + 6 + 30. fold is the general shape behind sum, product, min/max, and many other one-value reductions.

A plain function instead of a lambda

Any argument that expects a fn(...) value accepts a function reference — just name a top-level function:

use <collections/iter>

fn negate(i32 x) i32:
    return Result.Ok(0 - x)

fn main() i32:
    let List<i32> owed = List.new()
    owed.push(5)
    owed.push(8)
    # Pass a plain function by name -- no lambda needed.
    let List<i32> credited = map(owed, negate).realise(List.new())
    println(credited.get(0).realise(0))
    return Result.Ok(0)

Output:

-5

compose — glue two functions together

compose(g, f) builds a new function that runs g first, then feeds the result to f:

use <collections/iter>

fn babel(i32 x) i32:
    return Result.Ok(x + 1)

fn improbability(i32 x) i32:
    return Result.Ok(x * 2)

fn main() i32:
    # compose(g, f) runs g first, then f -- here babel, then improbability.
    let fn(i32) -> i32 pipeline = compose(babel, improbability).realise(improbability)
    println(pipeline(20).realise(-1))
    return Result.Ok(0)

Output:

42

compose(babel, improbability) returns a fn(i32) -> i32 that computes improbability(babel(20)) = (20 + 1) * 2. The returned function is a closure that captures both babel and improbability — exactly the capture-and-call machinery from Chapter 18, now packaged for you.

Two things to know

Element types are copy-only for now

The combinators work on copyable element types — integers, floats, bool, strings, and copyable structs. Owned element types (a List of dynamic arrays, for instance) are not supported yet, because filter re-inserts each kept element and map reads each one.

Annotate bare-parameter lambdas passed to a combinator

A bare-parameter lambda (|x| ...) cannot infer its type against a generic parameter, since the combinator's own type parameters are still being solved. Give the parameter a type (|i32 x| ...) or pass a function reference. To hand a generic function to a combinator, bind it to a typed local first:

let fn(i32) -> i32 id = identity   # fixes the instantiation
let List<i32> same = map(xs, id).realise(List.new())

What you learned

• use <collections/iter> brings in map, filter, fold, and compose — free generic functions, called as map(xs, f) rather than xs.map(f).
• collections/iter is the first Sushi-source standard-library module; the combinators monomorphize like any generic and cost nothing when unused.
• Each combinator takes a fn(...) value: a lambda (capturing or not) or a plain function reference.
• compose returns a closure that captures and calls the two functions you give it.
• Element types are copy-only for now; annotate bare-parameter lambdas, or bind a generic function to a typed local, when passing them to a combinator.