Implementing Collection

The built-in collections implement Collection through compiler intrinsics, and those aren’t going anywhere — they are the fastest path for Array and Map. But the trait needs only three methods, and all three are ordinary Graphix: any structure you can fold, you can give the whole collection API. This chapter is the reference for what those implementations look like written out, and what they cost.

The operations as loops

Over an array-backed structure, the operations are index tail recursions, compiled to a native loop:

// The collection operations written as plain Graphix loops over an
// array — the spellings a Collection implementation for your own
// array-backed type would use. Each is an index tail recursion, and the
// whole loop compiles to a native kernel.
// fold: the primitive (the loop pays its own bounds check, `$` and
// select per element; array::len is a fast call).
let rec fold_go = |a: Array<'a>, f: fn(acc: 'b, x: 'a) -> 'b, i: i64, acc: 'b| -> 'b
    select i < array::len(a) {
        true => fold_go(a, f, i + 1, f(acc, a[i]$)),
        false => acc
    };

// find: stops at the match, the early exit a fold cannot express. For
// a type of your own that is the point; against Array's intrinsic it
// wins only on a hit near the front.
let rec find_go = |a: Array<'a>, f: fn(x: 'a) -> bool, i: i64| -> ['a, null]
    select i < array::len(a) {
        false => null,
        true => select f(a[i]$) {
            true => a[i]$,
            false => find_go(a, f, i + 1)
        }
    };

// map: by construction over the length — at parity with the intrinsic.
let map_go = |a: Array<'a>, f: fn(x: 'a) -> 'b| -> Array<'b>
    array::init(array::len(a), |i| f(a[i]$));

let xs = [1, 2, 3, 4, 5];
let s = #[native] fold_go(xs, |acc, x| acc + x, 0, 0);
let m = select #[native] find_go(xs, |x| x > 3, 0) { null as _ => -1, x => x };
let d = #[native] map_go(xs, |x| x * 10);
println("sum=[s] found=[m] mapped=[d]");
sys::exit(s ~ 0)

fold is the primitive; the hand-written loop pays its own bounds check, $ and select per element, so it runs several times slower than the intrinsic. find as a loop stops at the match, an early exit the fold-derived default cannot express. That is what a Collection implementation for your own type gains; against Array’s intrinsic, which is faster per element and forks across cores, the loop wins only when the hit is near the front. map by construction over the length runs close to the intrinsic.

flat_map without the quadratic

The tempting derivation — fold with array::concat — copies the accumulator on every step and is O(n²) by construction. Cons onto a List instead and finish with one reverse walk:

// flat_map without the O(n²) of repeated array concatenation: cons
// every produced element onto a List (O(1) per element) and finish
// with one reverse walk into an array. Linear, and the nested fold
// fuses into one kernel with the outer loop.
let flat_map_go = |a: Array<'a>, f: fn(x: 'a) -> Array<'b>| -> Array<'b> {
    let nil: List<'b> = [<>];
    let l = array::fold(a, nil, |acc, x|
        array::fold(f(x), acc, |acc, y| list::cons(y, acc)));
    list::to_array_rev(l)
};

let r = #[native] flat_map_go([1, 2, 3], |x| [x, x * 10]);
println("[r]");
sys::exit(r ~ 0)

This is linear, and the nested fold fuses into one kernel with the outer loop — about 3.5x the intrinsic, all of it the per-element Cons construction.

A full implementation for your own type

A program-defined linear (or tree) structure implements the three required methods as natural recursions over its constructors and inherits map, filter, find, find_map and len from the defaults:

// A program-defined linear structure with a full Collection
// implementation: write the three required methods as natural
// recursions over the constructors and every derived method (map,
// filter, find, len, ...) comes for free. The tail-recursive fold
// runs as a native loop; the value-building recursions are an
// activation per element.
type L<'a> = [`C('a, L<'a>), `N];

let rec fold_l = |l: L<'a>, acc: 'b, f: fn(acc: 'b, x: 'a) -> 'b throws 'e|
    -> 'b throws 'e
    select l {
        `N => acc,
        `C(x, rest) => fold_l(rest, f(acc, x), f)
    };

let rec filter_map_l = |l: L<'a>, f: fn(x: 'a) -> Option<'b> throws 'e|
    -> L<'b> throws 'e
    select l {
        `N => `N,
        `C(x, rest) => select f(x) {
            null as _ => filter_map_l(rest, f),
            y => `C(y, filter_map_l(rest, f))
        }
    };

let rec append_l = |a: L<'a>, b: L<'a>| -> L<'a>
    select a { `N => b, `C(x, rest) => `C(x, append_l(rest, b)) };

let rec flat_map_l = |l: L<'a>, f: fn(x: 'a) -> L<'b> throws 'e|
    -> L<'b> throws 'e
    select l {
        `N => `N,
        `C(x, rest) => append_l(f(x), flat_map_l(rest, f))
    };

impl Collection for L<'_> {
    let fold = |l, init, f| fold_l(l, init, f);
    let filter_map = |l, f| filter_map_l(l, f);
    let flat_map = |l, f| flat_map_l(l, f)
};

use Collection::*;
let l: L<i64> = `C(1, `C(2, `C(3, `N)));
let doubled = map(l, |x| x * 2);
let s = #[native] fold(doubled, 0, |a, x| a + x);
let n = len(filter(l, |x| x > 1));
println("sum=[s] kept=[n]");
sys::exit(s ~ 0)

The tail-recursive fold_l compiles to a native loop over the conses; the value-building recursions (filter_map_l, append_l) are an activation per element — see Recursion. This shape is not a toy: the same spelling over the built-in List — written with list patterns, [<>] and [<x, rest..>] — runs faster than the list fold intrinsic at 100k elements (the intrinsic pays a convert-to-array boundary; the recursion just walks the conses).

The measured comparisons behind the numbers above live in bench/collection/README.md in the Graphix repository, one row per operation and derivation, re-run as the compiler moves.