Sequence

The one lazy iteration protocol: pull-based sequences with natural names.

A Sequence is a pull producer: a thunk that, when forced with (()), yields one Step – either SDone (exhausted) or SMore(x, rest), the next element x paired with the thunk producing the remainder. Nothing is materialized up front; each (()) advances the stream by one element. A transformer (map, filter, take, …) wraps a producer in a new producer that pulls, reshapes, and re-yields; a consumer (fold, sum, to_list, …) drives the producer to exhaustion and folds the elements into a value.

Type

type Step(a) = SDone | SMore(a, (Unit) -> Step(a))
Seq(a)       = (Unit) -> Step(a)          -- read `Seq(a)` in the prose as this

The step continuation is ordinary data, not an effect, so every combinator is a total pure function over Step. That is the whole reason this substrate exists: an earlier push design routed elements through a shared Emit effect, and a single Emit(a) label per scope made element-type changes, heterogeneous zip, and mixing two element types in one function unrepresentable. On pull Step the element type is a plain type parameter, so map : Seq(a) -> Seq(b) type-changes freely, zip : (Seq(a), Seq(b)) -> Seq((a, b)) is genuinely heterogeneous, and a consumer’s per-element function may perform any ambient effect (it runs directly, with no handler closing the row over it). Every combinator below exercises one of those, and the correctness corpus in tests/cases/run pins them on both backends.

Effect-polymorphic consumers

for_each’s function argument runs in the ambient row: for_each(s, \(x) -> println(x)) threads IO straight out with no annotation, because the driver is a plain recursion and installs no handler. This is the effectful-mapper case the push substrate could not express.

Naming and the import idiom

The combinators keep their natural names (map, filter, take, zip, …), which collide with Base’s eager List surface. That is why this module is opt-in and NOT in Base: the flat namespace has no shadowing, so the documented idiom is a qualified import at the use site:

import Sequence as Seq          -- qualified: Seq.map, Seq.filter, Seq.take
Seq.to_list(Seq.filter(Seq.map(Seq.range(1, 100), \(x) -> x * x), even))

A selective import Sequence (unfold, iterate) also works for names that do not clash with Base.

Fusion and allocation

A pull pipeline is correct and constant-space per stage. At -O1, each transformer stage allocates one SMore cons and one step thunk per element. At -O2, stream fusion collapses the supported range/map/filter/take and fold pipelines through the module boundary, so they allocate no intermediate step cells. The performance gates pin that zero slope; shapes outside the recognizer retain the per-stage allocation. The algebraic-effect EOp counter remains zero because pulling a sequence performs no effects. The eager Data.List surface fuses through FBIP reuse and remains the natural choice for strict traversal, while Sequence provides early exit and infinite producers.

Types

Step

type Step(a) = SDone | SMore(a, (Unit) -> Step(a))

Functions and Values

empty

empty : forall a. () -> (Unit) -> Sequence.Step(a)

The empty sequence: yields nothing.

Seq.to_list(Seq.empty())

[]

singleton

singleton : forall a. (a) -> (Unit) -> Sequence.Step(a)

The one-element sequence yielding x.

Seq.to_list(Seq.singleton(42))

[42]

range

range : (Int, Int) -> (Unit) -> Sequence.Step(Int)

The ascending integers in [lo, hi). Self-recursive: the continuation is the next range, so no element is built until pulled.

Seq.to_list(Seq.range(1, 5))

[1, 2, 3, 4]

from_list

from_list : forall a. (List(a)) -> (Unit) -> Sequence.Step(a)

The container boundary in: the elements of list xs, in order.

Seq.to_list(Seq.from_list([1, 2, 3]))

[1, 2, 3]

iterate

iterate : forall a. (a, (a) -> a) -> (Unit) -> Sequence.Step(a)

The infinite sequence x, f(x), f(f(x)), .... Bound it with take.

Seq.to_list(Seq.take(Seq.iterate(1, \(x) -> x * 2), 4))

[1, 2, 4, 8]

repeat

repeat : forall a. (a) -> (Unit) -> Sequence.Step(a)

The infinite sequence of x repeated. Bound it with take.

Seq.to_list(Seq.take(Seq.repeat(7), 3))

[7, 7, 7]

unfold

unfold : forall a b. (a, (a) -> Option((b, a))) -> (Unit) -> Sequence.Step(b)

The generator producer: yield x for each Some((x, seed')) that step returns from the running seed, stopping at None. Every finite producer is a special case; on pull Step a generator is just a fold over the seed, needing no coroutine or handler.

Seq.to_list(Seq.unfold(1, \(n) -> if n <= 3 then Some((n, n + 1)) else None))

[1, 2, 3]

map

map : forall a b. ((Unit) -> Sequence.Step(a), (a) -> b) -> (Unit) -> Sequence.Step(b)

Apply f to every element. Type-changing: Seq(a) -> Seq(b).

Seq.to_list(Seq.map(Seq.range(1, 4), \(x) -> x * x))

[1, 4, 9]

filter

filter : forall a. ((Unit) -> Sequence.Step(a), (a) -> Bool) -> (Unit) -> Sequence.Step(a)

Keep only the elements satisfying p.

Seq.to_list(Seq.filter(Seq.range(1, 7), \(x) -> mod(x, 2) == 0))

[2, 4, 6]

filter_map

filter_map : forall a b. ((Unit) -> Sequence.Step(a), (a) -> Option(b)) -> (Unit) -> Sequence.Step(b)

Map and filter in one pass: yield y for each f(x) == Some(y), dropping the Nones.

Seq.to_list(Seq.filter_map(Seq.range(1, 5), \(x) -> if x > 2 then Some(x * 10) else None))

[30, 40]

append

append : forall a. ((Unit) -> Sequence.Step(a), (Unit) -> Sequence.Step(a)) -> (Unit) -> Sequence.Step(a)

Concatenate two sequences: all of s, then all of t.

Seq.to_list(Seq.append(Seq.range(1, 3), Seq.range(10, 12)))

[1, 2, 10, 11]

flat_map

flat_map : forall a b. ((Unit) -> Sequence.Step(a), (a) -> (Unit) -> Sequence.Step(b)) -> (Unit) -> Sequence.Step(b)

For each element x, splice in the sequence f(x).

Seq.to_list(Seq.flat_map(Seq.range(1, 4), \(x) -> Seq.range(0, x)))

[0, 0, 1, 0, 1, 2]

take

take : forall a. ((Unit) -> Sequence.Step(a), Int) -> (Unit) -> Sequence.Step(a)

The first n elements, stopping the producer once the budget is spent.

Seq.to_list(Seq.take(Seq.range(1, 100), 3))

[1, 2, 3]

drop

drop : forall a. ((Unit) -> Sequence.Step(a), Int) -> (Unit) -> Sequence.Step(a)

Skip the first n elements, yielding the rest.

Seq.to_list(Seq.drop(Seq.range(1, 6), 2))

[3, 4, 5]

take_while

take_while : forall a. ((Unit) -> Sequence.Step(a), (a) -> Bool) -> (Unit) -> Sequence.Step(a)

The longest prefix whose elements satisfy p; stops at the first failure.

Seq.to_list(Seq.take_while(Seq.range(1, 10), \(x) -> x < 4))

[1, 2, 3]

drop_while

drop_while : forall a. ((Unit) -> Sequence.Step(a), (a) -> Bool) -> (Unit) -> Sequence.Step(a)

Drop the longest prefix satisfying p, yielding the rest.

Seq.to_list(Seq.drop_while(Seq.range(1, 6), \(x) -> x < 3))

[3, 4, 5]

dedup

dedup : forall e1 a. ((Unit) -> Sequence.Step(Int) ! {e1}) -> (a) -> Sequence.Step(Int) ! {e1}

Drop consecutive duplicates, keeping the first of each run (needs Eq(a)). Left unsigned so the Eq(a) constraint is inferred from ==.

Seq.to_list(Seq.dedup(Seq.from_list([1, 1, 2, 2, 2, 3])))

[1, 2, 3]

enumerate

enumerate : forall a. ((Unit) -> Sequence.Step(a)) -> (Unit) -> Sequence.Step((Int, a))

Pair each element with its zero-based index, yielding (i, x).

Seq.to_list(Seq.enumerate(Seq.from_list(["a", "b"])))

[(0, a), (1, b)]

scan

scan : forall a b. ((Unit) -> Sequence.Step(a), b, (b, a) -> b) -> (Unit) -> Sequence.Step(b)

The running left-fold, streamed: yield z, then each successive accumulator.

Seq.to_list(Seq.scan(Seq.range(1, 4), 0, \(acc, x) -> acc + x))

[0, 1, 3, 6]

interleave

interleave : forall a. ((Unit) -> Sequence.Step(a), (Unit) -> Sequence.Step(a)) -> (Unit) -> Sequence.Step(a)

Alternate elements of s and t (s0, t0, s1, t1, ...); when one runs out, yield the whole remainder of the other. Streamed, no materialization.

Seq.to_list(Seq.interleave(Seq.range(1, 4), Seq.range(10, 12)))

[1, 10, 2, 11, 3]

zip

zip : forall a b. ((Unit) -> Sequence.Step(a), (Unit) -> Sequence.Step(b)) -> (Unit) -> Sequence.Step((a, b))

Pair two sequences element-wise, stopping at the shorter. Genuinely heterogeneous: Seq(a) and Seq(b) yield Seq((a, b)).

Seq.to_list(Seq.zip(Seq.range(1, 4), Seq.from_list(["a", "b", "c"])))

[(1, a), (2, b), (3, c)]

zip_with

zip_with : forall a b c. ((Unit) -> Sequence.Step(a), (Unit) -> Sequence.Step(b), (a, b) -> c) -> (Unit) -> Sequence.Step(c)

Combine two sequences element-wise with f, stopping when either runs out. Heterogeneous in both operand types.

Seq.to_list(Seq.zip_with(Seq.range(1, 4), Seq.range(10, 13), \(a, b) -> a + b))

[11, 13, 15]

chunk

chunk : forall a. ((Unit) -> Sequence.Step(a), Int) -> (Unit) -> Sequence.Step(List(a))

Group elements into consecutive lists of length n (the final chunk may be shorter). Pulls one group at a time, holding only the current group.

Seq.to_list(Seq.chunk(Seq.range(1, 6), 2))

[[1, 2], [3, 4], [5]]

window

window : forall a. ((Unit) -> Sequence.Step(a), Int) -> (Unit) -> Sequence.Step(List(a))

Every contiguous length-n sliding window, in order. Fewer than n elements yields nothing. Holds one window (n elements) at a time.

Seq.to_list(Seq.window(Seq.range(1, 5), 2))

[[1, 2], [2, 3], [3, 4]]

fold

fold : forall a b. ((Unit) -> Sequence.Step(b), a, (a, b) -> a) -> a

Left-fold the sequence with f from initial accumulator z.

Seq.fold(Seq.range(1, 5), 0, \(acc, x) -> acc + x)

10

for_each

for_each : forall e0 a. ((Unit) -> Sequence.Step(a), (a) -> Unit ! {e0}) -> Unit ! {e0}

Run f for its effects on each element, in order. Effect-polymorphic: f runs in the ambient row (no handler intervenes), so for_each(s, \(x) -> println(x)) threads IO out. The explicit {| e} row matters: unsigned, the self-recursion would infer f as pure and reject an effectful body.

Seq.for_each(Seq.range(1, 4), \(x) -> println(show(x)))

1
2
3

sum

sum : ((Unit) -> Sequence.Step(Int)) -> Int

Sum a sequence of integers.

Seq.sum(Seq.range(1, 5))

10

product

product : ((Unit) -> Sequence.Step(Int)) -> Int

Product of a sequence of integers.

Seq.product(Seq.range(1, 5))

24

count

count : forall a. ((Unit) -> Sequence.Step(a)) -> Int

The number of elements.

Seq.count(Seq.range(1, 100))

99

to_list

to_list : forall a. ((Unit) -> Sequence.Step(a)) -> List(a)

Collect the sequence into a list, in order. The container boundary out.

Seq.to_list(Seq.map(Seq.range(1, 4), \(x) -> x + 100))

[101, 102, 103]

head

head : forall e0 a. ((Unit) -> Sequence.Step(a) ! {e0}) -> Option(a) ! {e0}

The first element, or None if the sequence is empty.

Seq.head(Seq.range(5, 10))

Some(5)

find

find : forall a. ((Unit) -> Sequence.Step(a), (a) -> Bool) -> Option(a)

The first element satisfying p, or None; stops the producer at the match.

Seq.find(Seq.range(1, 100), \(x) -> x > 10)

Some(11)

any

any : forall a. ((Unit) -> Sequence.Step(a), (a) -> Bool) -> Bool

True when some element satisfies p; short-circuits.

Seq.any(Seq.range(1, 5), \(x) -> x == 3)

true

all

all : forall a. ((Unit) -> Sequence.Step(a), (a) -> Bool) -> Bool

True when every element satisfies p; short-circuits on the first failure.

Seq.all(Seq.range(1, 5), \(x) -> x < 10)

true

from_bytes

from_bytes : (Wire.Bytes) -> (Unit) -> Sequence.Step(Int)

The bytes of bs as a sequence of ints in 0..255, in order.

to_bytes

to_bytes : ((Unit) -> Sequence.Step(Int)) -> Wire.Bytes

Collect a sequence of ints (each masked to a byte) into a Bytes. The Bytes container boundary out.