Source src/silo:std.collections

1##! Collection trait hierarchy and generic collection helpers.
2##!
3##! Declares the abstract-collection traits (`Foldable`, `Mappable`,
4##! `Filterable`, `Keyed`, `Chainable`, `Indexed`, `Zippable`) and the
5##! category aliases (`Seq`, `Map`, `Set`) that classify concrete types
6##! like `Vec`, `HashMap`, and `HashSet`.
7
8:use
9  :open core Bool AnyInt Vec Pair Option None Some RangeBoth Ordering Less Equal Greater Result Ok Err Unit
10  :open collections.hashmap HashMap
11  :open collections.hashset HashSet
12  :open traits Eq Add Not Ord Default
13  :open effects.random random-gen-u64
14:end
15
16# si[impl coll.hashmap.hash-state+2]
17## Opaque, seeded hasher state used internally by `HashMap` and `HashSet`
18## for HashDoS resistance. The canonical constructor `(HashState .new)`
19## draws entropy via `+Random`. The free fn `hash-state-new` is retained
20## as a zero-seed helper for tests that need a deterministic `HashState`
21## without carrying an effect.
22##
23## Deferred (lands with the HashMap/HashSet `.default` rewire):
24##   - Threading `+Random` through `(HashMap .default)` / `(HashSet
25##     .default)`. That is a prelude-semver change (both types drop out
26##     of the prelude) and cascades through every construction site, so
27##     it is gated behind effect-handler infra.
28:record(pub) HashState
29  .seed AnyInt
30:end
31
32# si[impl coll.hashmap.hash-state+2]
33## Construct a `HashState` seeded from a fresh `+Random` draw. This is
34## the spec-canonical form of `(HashState .new)`; callers that need a
35## deterministic zero-seeded state (e.g. bootstrap tests) use
36## `hash-state-new` instead.
37:impl HashState
38  .new ( -> HashState ) +Random
39    random-gen-u64 HashState ;
40:end
41
42# si[impl coll.hashmap.hash-state+2]
43## Construct a `HashState` with a fixed zero seed. Deterministic sibling
44## of `(HashState .new)` used by stdlib code that needs a `HashState`
45## without carrying `+Random`.
46## ( -> HashState )
47:fn(pub) hash-state-new ( -> HashState )
48  0 HashState
49:end
50
51# si[impl coll.hashmap.hash-state+2]
52# si[impl lang.default+1]
53## `HashMap`'s `.default` MUST draw a seeded `HashState` via
54## `(HashState .new)`, carrying `+Random`. The HashState is produced
55## and dropped here because `hashmap-new-intrinsic` does not yet
56## accept a state argument (the runtime HashMap does not thread the
57## seed through its bucket hasher). The declared `+Random` effect is
58## still load-bearing: it documents that `HashMap` construction is
59## non-deterministic per the HashDoS-resistance contract and forces
60## callers to either sit inside a `+Random` handler or use an
61## explicit zero-seed path through `hash-state-new` +
62## `hashmap-new-intrinsic`.
63:impl Default (HashMap key val)
64  .default ( -> (HashMap key val) ) +Random
65    (HashState .new) drop hashmap-new-intrinsic ;
66:end
67
68# si[impl coll.hashmap.hash-state+2]
69# si[impl lang.default+1]
70## `HashSet`'s `.default` mirrors `HashMap`'s: draws `(HashState .new)`
71## and discards the state, carrying `+Random`.
72:impl Default (HashSet elem)
73  .default ( -> (HashSet elem) ) +Random
74    (HashState .new) drop hashset-new-intrinsic ;
75:end
76
77## Classic while-loop word: repeatedly evaluate `cond`; while it yields
78## `true`, invoke `body`. Stops the first time `cond` produces `false`.
79## ( [..s -> ..s Bool] [..s -> ..s] -> )
80:fn(pub) while ( [..s -> ..s Bool] [..s -> ..s] -> )
81  pop-> body pop-> cond
82  :loop cond .call not :if :break :end body .call :end
83:end
84
85# si[impl coll.foldable]
86# si[impl coll.foldable.default]
87## Trait for collections whose elements can be consumed by folding.
88## The most general collection surface: any type that can produce its
89## elements one at a time implements `Foldable`. `.fold` and `.for-each`
90## are required; `.any`, `.all`, `.count` are defaults derived from
91## `.fold`.
92@lang(foldable)
93:trait(pub) Foldable
94  ## Reduce the collection to a single value by threading `acc` through
95  ## a binary quotation applied to each element in iteration order.
96  ## ( (Self elem) acc [acc elem -> acc] -> acc )
97  .fold ( (Self elem) acc [acc elem -> acc] -> acc )
98  ## Apply a quotation to each element for its effects; no result value.
99  ## ( (Self elem) [elem ->] -> )
100  .for-each ( (Self elem) [elem ->] -> )
101  ## Return `true` if `pred` holds for any element.
102  ## ( (Self elem) [elem -> Bool] -> Bool )
103  .any ( (Self elem) [elem -> Bool] -> Bool )
104    pop-> pred false [ pop-> e pop-> acc e pred .call acc or ] .fold ;
105  ## Return `true` if `pred` holds for every element.
106  ## ( (Self elem) [elem -> Bool] -> Bool )
107  .all ( (Self elem) [elem -> Bool] -> Bool )
108    pop-> pred true [ pop-> e pop-> acc e pred .call acc and ] .fold ;
109  ## Return the number of elements.
110  ## ( (Self elem) -> AnyInt )
111  .count ( (Self elem) -> AnyInt )
112    0 [ drop 1 + ] .fold ;
113  ## Return `Some elem` for the first element, else `None` on empty.
114  ## Not spec'd but a natural Foldable default.
115  ## ( (Self elem) -> (Option elem) )
116  .first ( (Self elem) -> (Option elem) )
117    None [ pop-> e pop-> acc
118      acc :match
119        | Some x => x Some
120        | None   => e Some
121      :end
122    ] .fold ;
123  ## Return `Some elem` for the last element, else `None` on empty.
124  ## Not spec'd but a natural Foldable default.
125  ## ( (Self elem) -> (Option elem) )
126  .last ( (Self elem) -> (Option elem) )
127    None [ pop-> e drop e Some ] .fold ;
128  # si[impl stdlib.iter.find+1]
129  ## Return `Some elem` for the first element satisfying `pred`, else
130  ## `None`. No short-circuit — visits every element; keeps the first
131  ## match.
132  ## ( (Self elem) [elem -> Bool] -> (Option elem) )
133  .find ( (Self elem) [elem -> Bool] -> (Option elem) )
134    pop-> pred
135    None [ pop-> e pop-> acc
136      acc :match
137        | Some x => x Some
138        | None   => e pred .call :if e Some :else None :end
139      :end
140    ] .fold ;
141  # si[impl stdlib.iter.reduce]
142  ## Reduce the collection with a binary combiner. Returns `None` on empty.
143  ## ( (Self elem) [elem elem -> elem] -> (Option elem) )
144  .reduce ( (Self elem) [elem elem -> elem] -> (Option elem) )
145    pop-> f
146    None [ pop-> e pop-> acc
147      acc :match
148        | Some x => x e f .call Some
149        | None   => e Some
150      :end
151    ] .fold ;
152  # si[impl stdlib.iter.find-map]
153  ## Return `Some b` for the first quotation call that yields `Some b`.
154  ## Produces `None` if every element maps to `None`.
155  ## ( (Self elem) [elem -> (Option b)] -> (Option b) )
156  .find-map ( (Self elem) [elem -> (Option b)] -> (Option b) )
157    pop-> f
158    None [ pop-> e pop-> acc
159      acc :match
160        | Some x => x Some
161        | None   => e f .call
162      :end
163    ] .fold ;
164  # si[impl stdlib.iter.try-fold]
165  ## Short-circuiting fold. Threads the accumulator through a combiner
166  ## returning `(Result acc err)`; stops at the first `Err` and returns
167  ## it unchanged. On empty, returns `init Ok`.
168  ## ( (Self elem) acc [acc elem -> (Result acc err)] -> (Result acc err) )
169  .try-fold ( (Self elem) acc [acc elem -> (Result acc err)] -> (Result acc err) )
170    pop-> f pop-> init
171    init Ok [ pop-> e pop-> r
172      r :match
173        | Ok a   => a e f .call
174        | Err er => er Err
175      :end
176    ] .fold ;
177  # si[impl stdlib.iter.try-for-each]
178  ## Short-circuiting for-each. Calls an effectful quotation returning
179  ## `(Result Unit err)` per element; stops at the first `Err`. On an
180  ## empty collection or all-`Ok` walk, returns `unit Ok`.
181  ## ( (Self elem) [elem -> (Result Unit err)] -> (Result Unit err) )
182  .try-for-each ( (Self elem) [elem -> (Result Unit err)] -> (Result Unit err) )
183    pop-> f
184    unit Ok [ pop-> e pop-> r
185      r :match
186        | Ok _   => e f .call
187        | Err er => er Err
188      :end
189    ] .fold ;
190  # si[impl stdlib.iter.try-reduce]
191  ## Short-circuiting reduce. Empty collection yields `None Ok`. The
192  ## first element seeds the reduction; subsequent elements are
193  ## combined with the current value via `f`, whose `(Result elem err)`
194  ## result short-circuits on `Err`.
195  ## ( (Self elem) [elem elem -> (Result elem err)] -> (Result (Option elem) err) )
196  .try-reduce ( (Self elem) [elem elem -> (Result elem err)] -> (Result (Option elem) err) )
197    pop-> f
198    None Ok [ pop-> e pop-> r
199      r :match
200        | Err er => er Err
201        | Ok maybe => maybe :match
202            | None   => e Some Ok
203            | Some x => x e f .call :match
204                | Ok y    => y Some Ok
205                | Err er2 => er2 Err
206              :end
207          :end
208      :end
209    ] .fold ;
210  # si[impl stdlib.iter.min-by+1]
211  ## Return `Some elem` for the minimum element per comparator, else `None`.
212  ## ( (Self elem) [elem elem -> Ordering] -> (Option elem) )
213  .min-by ( (Self elem) [elem elem -> Ordering] -> (Option elem) )
214    pop-> cmp
215    [ pop-> rhs pop-> lhs
216      lhs rhs cmp .call :match
217        | Greater => rhs
218        | Less    => lhs
219        | Equal   => lhs
220      :end
221    ] .reduce ;
222  # si[impl stdlib.iter.max-by+1]
223  ## Return `Some elem` for the maximum element per comparator, else `None`.
224  ## ( (Self elem) [elem elem -> Ordering] -> (Option elem) )
225  .max-by ( (Self elem) [elem elem -> Ordering] -> (Option elem) )
226    pop-> cmp
227    [ pop-> rhs pop-> lhs
228      lhs rhs cmp .call :match
229        | Greater => lhs
230        | Less    => rhs
231        | Equal   => lhs
232      :end
233    ] .reduce ;
234  # si[impl stdlib.iter.enumerate+1]
235  ## Pair each element with its zero-based index. Fold with a
236  ## `(Pair AnyInt (Vec (Pair AnyInt elem)))` accumulator: `.a`
237  ## tracks the next index, `.b` collects `Pair idx elem` entries.
238  ## Returns the accumulator Pair as-is (index on `.a`, entries on
239  ## `.b`); projecting `.b` inline in the body trips the checker
240  ## on a spurious `elem = Vec (Pair AnyInt elem)` self-reference,
241  ## and projecting at the call site also loses type info. Callers
242  ## that need just the Vec bind with `pop->` and project then.
243  ## ( (Self elem) -> (Pair AnyInt (Vec (Pair AnyInt elem))) )
244  .enumerate ( (Self elem) -> (Pair AnyInt (Vec (Pair AnyInt elem))) )
245    0 (Vec .default) Pair [ pop-> e pop-> acc
246      acc .a pop-> i
247      acc .b pop-> vec
248      i 1 + vec i e Pair .push Pair
249    ] .fold ;
250  # si[impl stdlib.iter.position+1]
251  ## Return `Some AnyInt` for the zero-based index of the first element
252  ## satisfying `pred`, else `None`. Fold with a
253  ## `(Pair AnyInt (Option AnyInt))` accumulator.
254  ## ( (Self elem) [elem -> Bool] -> (Option AnyInt) )
255  .position ( (Self elem) [elem -> Bool] -> (Option AnyInt) )
256    pop-> pred
257    0 None Pair [ pop-> e pop-> acc
258      acc .a pop-> i
259      acc .b pop-> hit
260      hit :match
261        | Some x => i 1 + x Some Pair
262        | None   => e pred .call
263          :if i 1 + i Some Pair
264          :else i 1 + None Pair
265          :end
266      :end
267    ] .fold
268    .b ;
269  # si[impl stdlib.iter.take+1]
270  ## Return the first `n` elements as a `Vec`. Fold with a
271  ## `(Pair AnyInt (Vec elem))` accumulator; once the collected count
272  ## reaches `n`, subsequent elements are ignored.
273  ## ( (Self elem) AnyInt -> (Vec elem) )
274  .take ( (Self elem) AnyInt -> (Vec elem) )
275    pop-> n
276    0 (Vec .default) Pair [ pop-> e pop-> acc
277      acc .a pop-> i
278      acc .b pop-> vec
279      i n < :if
280        i 1 + vec e .push Pair
281      :else
282        i 1 + vec Pair
283      :end
284    ] .fold
285    .b ;
286  # si[impl stdlib.iter.skip+1]
287  ## Return all elements after the first `n`. Fold with a
288  ## `(Pair AnyInt (Vec elem))` accumulator; elements are pushed only
289  ## once the seen-count has reached `n`.
290  ## ( (Self elem) AnyInt -> (Vec elem) )
291  .skip ( (Self elem) AnyInt -> (Vec elem) )
292    pop-> n
293    0 (Vec .default) Pair [ pop-> e pop-> acc
294      acc .a pop-> i
295      acc .b pop-> vec
296      i n < :if
297        i 1 + vec Pair
298      :else
299        i 1 + vec e .push Pair
300      :end
301    ] .fold
302    .b ;
303  # si[impl stdlib.iter.partition+1]
304  ## Split elements by a predicate into two `Vec`s: the deeper Vec
305  ## contains elements where `pred` returned `true`, the top Vec
306  ## contains the rest. Matches spec: two Seqs on stack.
307  ## ( (Self elem) [elem -> Bool] -> (Vec elem la) (Vec elem lb) )
308  .partition ( (Self elem) [elem -> Bool] -> (Vec elem la) (Vec elem lb) )
309    pop-> pred
310    (Vec .default) (Vec .default) Pair [ pop-> e pop-> acc
311      acc .a pop-> trues
312      acc .b pop-> falses
313      e pred .call :if
314        trues e .push falses Pair
315      :else
316        trues falses e .push Pair
317      :end
318    ] .fold
319    pop-> result
320    result .a result .b ;
321  # si[impl stdlib.iter.take-while+1]
322  ## Take elements from the start as long as `pred` returns `true`.
323  ## The first element for which `pred` returns `false` stops collection
324  ## — no later elements are included, even if they would match. Fold
325  ## with a `(Pair Bool (Vec elem))` accumulator: `.a` is the still-
326  ## taking flag, `.b` is the collected Vec. Once the flag flips false
327  ## it stays false.
328  ## ( (Self elem) [elem -> Bool] -> (Vec elem) )
329  .take-while ( (Self elem) [elem -> Bool] -> (Vec elem) )
330    pop-> pred
331    true (Vec .default) Pair [ pop-> e pop-> acc
332      acc .a pop-> taking
333      acc .b pop-> vec
334      taking :if
335        e pred .call :if
336          true vec e .push Pair
337        :else
338          false vec Pair
339        :end
340      :else
341        false vec Pair
342      :end
343    ] .fold
344    .b ;
345  # si[impl stdlib.iter.skip-while+1]
346  ## Skip elements from the start as long as `pred` returns `true`.
347  ## Once `pred` returns `false` for some element, that element and
348  ## every element after it are collected regardless of the predicate.
349  ## Fold with a `(Pair Bool (Vec elem))` accumulator: `.a` is the
350  ## still-skipping flag, `.b` is the collected Vec.
351  ## ( (Self elem) [elem -> Bool] -> (Vec elem) )
352  .skip-while ( (Self elem) [elem -> Bool] -> (Vec elem) )
353    pop-> pred
354    true (Vec .default) Pair [ pop-> e pop-> acc
355      acc .a pop-> skipping
356      acc .b pop-> vec
357      skipping :if
358        e pred .call :if
359          true vec Pair
360        :else
361          false vec e .push Pair
362        :end
363      :else
364        false vec e .push Pair
365      :end
366    ] .fold
367    .b ;
368  # si[impl stdlib.iter.min-by-key]
369  ## Return `Some elem` for the element with the smallest key
370  ## extracted by `f`, else `None` on an empty collection. Fold with
371  ## an `(Option (Pair elem key))` accumulator so the `.a` / `.b`
372  ## field projections pin the tuple shape through the fold. Uses
373  ## `.<` on keys — the `(Ord key key)` constraint must supply it.
374  ## ( (Self elem) [elem -> key] -> (Option elem) ) { (Ord key key) }
375  .min-by-key ( (Self elem) [elem -> key] -> (Option elem) ) { (Ord key key) }
376    pop-> f
377    None [ pop-> e pop-> acc
378      e f .call pop-> k
379      acc :match
380        | None    => e k Pair Some
381        | Some bp =>
382            bp .a pop-> be
383            bp .b pop-> bk
384            k bk .< :if e k Pair Some :else be bk Pair Some :end
385      :end
386    ] .fold
387    :match
388      | None    => None
389      | Some bp => bp .a Some
390    :end ;
391  # si[impl stdlib.iter.max-by-key]
392  ## Return `Some elem` for the element with the largest key
393  ## extracted by `f`, else `None` on an empty collection. Mirrors
394  ## `.min-by-key` but replaces `.<` with `.>`.
395  ## ( (Self elem) [elem -> key] -> (Option elem) ) { (Ord key key) }
396  .max-by-key ( (Self elem) [elem -> key] -> (Option elem) ) { (Ord key key) }
397    pop-> f
398    None [ pop-> e pop-> acc
399      e f .call pop-> k
400      acc :match
401        | None    => e k Pair Some
402        | Some bp =>
403            bp .a pop-> be
404            bp .b pop-> bk
405            k bk .> :if e k Pair Some :else be bk Pair Some :end
406      :end
407    ] .fold
408    :match
409      | None    => None
410      | Some bp => bp .a Some
411    :end ;
412  ## Count the elements for which `pred` returns `true`. Pure fold
413  ## with an integer counter. Not specced as its own iter rule — this
414  ## is a natural Foldable default that sits between `.count`
415  ## (unconditional) and `.any`/`.all` (boolean aggregation).
416  ## ( (Self elem) [elem -> Bool] -> AnyInt )
417  .count-where ( (Self elem) [elem -> Bool] -> AnyInt )
418    pop-> pred
419    0 [ pop-> e pop-> acc
420      e pred .call :if acc 1 + :else acc :end
421    ] .fold ;
422  # si[impl stdlib.iter.filter-map]
423  ## Fused filter+map: call `f` on each element and collect the
424  ## `Some` payloads into a `Vec`, skipping `None`s. Wraps the
425  ## output Vec in a single-field Pair-like accumulator (the
426  ## unit pairing) so the checker pins the element type through
427  ## fold — bare `(Vec .default)` as the fold acc leaves the
428  ## element polymorphic and `.push` fails to resolve at install.
429  ## ( (Self elem) [elem -> (Option b)] -> (Vec b) )
430  .filter-map ( (Self elem) [elem -> (Option b)] -> (Vec b) )
431    pop-> f
432    unit (Vec .default) Pair [ pop-> e pop-> acc
433      acc .a pop-> u
434      acc .b pop-> vec
435      e f .call :match
436        | Some x => u vec x .push Pair
437        | None   => u vec Pair
438      :end
439    ] .fold
440    .b ;
441  # si[impl stdlib.iter.map-while]
442  ## Like `.filter-map`, but the first `None` result stops iteration;
443  ## subsequent elements are not consulted. Fold with a
444  ## `(Pair Bool (Vec b))` accumulator — `.a` is the still-taking flag,
445  ## `.b` is the collected Vec.
446  ## ( (Self elem) [elem -> (Option b)] -> (Vec b) )
447  .map-while ( (Self elem) [elem -> (Option b)] -> (Vec b) )
448    pop-> f
449    true (Vec .default) Pair [ pop-> e pop-> acc
450      acc .a pop-> taking
451      acc .b pop-> vec
452      taking :if
453        e f .call :match
454          | Some x => true vec x .push Pair
455          | None   => false vec Pair
456        :end
457      :else
458        false vec Pair
459      :end
460    ] .fold
461    .b ;
462  # si[impl stdlib.iter.is-partitioned]
463  ## Return `true` if every element for which `pred` returns `true`
464  ## appears before every element for which it returns `false`. An
465  ## empty collection is considered partitioned. Fold with a
466  ## `(Pair Bool Bool)` accumulator: `.a` is the still-ok flag,
467  ## `.b` records whether any `false`-predicate element has been
468  ## observed yet. Seeing a `true` after a `false` breaks the
469  ## invariant.
470  ## ( (Self elem) [elem -> Bool] -> Bool )
471  .is-partitioned ( (Self elem) [elem -> Bool] -> Bool )
472    pop-> pred
473    true false Pair [ pop-> e pop-> acc
474      acc .a pop-> ok
475      acc .b pop-> seen-false
476      ok :if
477        e pred .call :if
478          seen-false :if
479            false true Pair
480          :else
481            true false Pair
482          :end
483        :else
484          true true Pair
485        :end
486      :else
487        false true Pair
488      :end
489    ] .fold
490    .a ;
491  # si[impl stdlib.iter.scan]
492  ## Stateful transform. Thread an initial state through a stepper
493  ## `[state elem -> state (Option result)]`. Each `Some r`
494  ## contributes `r` to the output `Vec`; the first `None` stops
495  ## iteration. Fold with a `(Pair (Option state) (Vec result))`
496  ## accumulator — outer `.a` is `Some state` while running and
497  ## `None` once terminated, outer `.b` is the collected output.
498  ## The `:match` on `.a` pins the Option shape through fold so
499  ## the body's field dispatch and `.push` on the Vec resolve.
500  ## ( (Self elem) state [state elem -> state (Option result)] -> (Vec result) )
501  .scan ( (Self elem) state [state elem -> state (Option result)] -> (Vec result) )
502    pop-> f pop-> init
503    init Some (Vec .default) Pair [ pop-> e pop-> acc
504      acc .a pop-> mstate
505      acc .b pop-> vec
506      mstate :match
507        | None   => None vec Pair
508        | Some s =>
509            s e f .call pop-> opt pop-> s2
510            opt :match
511              | Some r => s2 Some vec r .push Pair
512              | None   => None vec Pair
513            :end
514      :end
515    ] .fold
516    .b ;
517  # si[impl stdlib.iter.step-by]
518  ## Return every `stride`-th element starting with the first (index 0).
519  ## Fold with a `(Pair AnyInt (Vec elem))` accumulator: `.a` is the
520  ## running element index, `.b` is the collected output. An element is
521  ## included when `i mod stride = 0`. A stride of 1 returns every
522  ## element; the spec flags stride=0 as a compile-time error — this
523  ## default doesn't enforce that at the trait level.
524  ## ( (Self elem) AnyInt -> (Vec elem) )
525  .step-by ( (Self elem) AnyInt -> (Vec elem) )
526    pop-> stride
527    0 (Vec .default) Pair [ pop-> e pop-> acc
528      acc .a pop-> i
529      acc .b pop-> vec
530      i stride mod 0 = :if
531        i 1 + vec e .push Pair
532      :else
533        i 1 + vec Pair
534      :end
535    ] .fold
536    .b ;
537  # si[impl stdlib.iter.rposition]
538  ## Return `Some AnyInt` for the zero-based index of the last element
539  ## satisfying `pred`, else `None`. Fold visits every element,
540  ## overwriting the tracked match-index each time the predicate holds.
541  ## Accumulator is `(Pair AnyInt (Option AnyInt))`: `.a` is the running
542  ## index, `.b` is the most recent matching index (or `None`).
543  ## ( (Self elem) [elem -> Bool] -> (Option AnyInt) )
544  .rposition ( (Self elem) [elem -> Bool] -> (Option AnyInt) )
545    pop-> pred
546    0 None Pair [ pop-> e pop-> acc
547      acc .a pop-> i
548      acc .b pop-> last
549      e pred .call :if
550        i 1 + i Some Pair
551      :else
552        i 1 + last Pair
553      :end
554    ] .fold
555    .b ;
556  # si[impl stdlib.iter.chunks-n]
557  ## Partition a Foldable into fixed-size chunks. The last chunk MAY
558  ## have fewer than `n` elements if the input length is not a
559  ## multiple of `n`. Default is a stub; real body lives in the
560  ## `Foldable (Vec elem | len)` impl override where the element
561  ## type and outer accumulator are concretely bound.
562  ## ( (Self elem) AnyInt -> (Vec (Vec elem)) )
563  .chunks-n ( (Self elem) AnyInt -> (Vec (Vec elem)) )
564    drop drop (Vec .default) ;
565  # si[impl stdlib.iter.intersperse]
566  ## Insert `sep` between every adjacent pair of input elements. An
567  ## input with fewer than two elements MUST NOT include the separator.
568  ## Fold with a `(Pair Bool (Vec elem))` accumulator: `.a` tracks
569  ## whether the next element is the first (no leading separator);
570  ## `.b` is the collected output. The first element is pushed alone,
571  ## subsequent elements are pushed after a separator.
572  ## ( (Self elem) elem -> (Vec elem) )
573  .intersperse ( (Self elem) elem -> (Vec elem) )
574    pop-> sep
575    true (Vec .default) Pair [ pop-> e pop-> acc
576      acc .a pop-> first
577      acc .b pop-> vec
578      first :if
579        false vec e .push Pair
580      :else
581        false vec sep .push e .push Pair
582      :end
583    ] .fold
584    .b ;
585  # si[impl stdlib.iter.unzip]
586  ## Split a Foldable of `Pair a b` into two Vecs of the `.a` / `.b`
587  ## components. Default is a stub; real body lives in the
588  ## `Foldable (Vec elem | len)` impl override where the element is
589  ## concretely Pair-shaped.
590  ## ( (Self (Pair a b)) -> (Pair (Vec a) (Vec b)) )
591  .unzip ( (Self (Pair a b)) -> (Pair (Vec a) (Vec b)) )
592    drop (Vec .default) (Vec .default) Pair ;
593  # si[impl stdlib.iter.flatten+1]
594  ## Concatenate a Foldable-of-Vecs into a single flat `Vec`. Default
595  ## is a stub; real body lives in the Vec impl override (requires
596  ## the element to be Vec-shaped).
597  ## ( (Self (Vec elem n)) -> (Vec elem) )
598  .flatten ( (Self (Vec elem n)) -> (Vec elem) )
599    drop (Vec .default) ;
600  # si[impl stdlib.iter.flat-map+1]
601  ## Map each element to a `Vec` via `f`, then concatenate. Default
602  ## is a stub; real body lives in the Vec impl override.
603  ## ( (Self elem) [elem -> (Vec b n)] -> (Vec b) )
604  .flat-map ( (Self elem) [elem -> (Vec b n)] -> (Vec b) )
605    drop drop (Vec .default) ;
606:end
607
608:impl Foldable (Vec elem len)
609  .fold ( (Vec elem len) acc [acc elem -> acc] -> acc )
610    pop-> f pop-> acc pop-> vec 0 pop-> i
611    :loop i vec .len = :if acc :ret :end
612      acc i vec .get f .call pop-> acc
613      i 1 + pop-> i
614    :end ;
615  .for-each ( (Vec elem len) [elem ->] -> )
616    pop-> f pop-> vec 0 pop-> i
617    :loop i vec .len = :if :ret :end
618      i vec .get f .call
619      i 1 + pop-> i
620    :end ;
621  # si[impl stdlib.iter.flatten+1]
622  ## Vec-specific flatten: nested fold pushing inner Vec's elements
623  ## into the outer accumulator. Element type is concretely
624  ## Vec-shaped here, so `.push` on the accumulator resolves.
625  .flatten ( (Vec (Vec inner-elem)) -> (Vec inner-elem) )
626    (Vec .default) [ pop-> inner pop-> acc
627      acc inner [ pop-> e pop-> acc2 acc2 e .push ] .fold
628    ] .fold ;
629  # si[impl stdlib.iter.flat-map+1]
630  ## Vec-specific flat-map: call `f` per element, flatten the results.
631  .flat-map ( (Vec elem) [elem -> (Vec b)] -> (Vec b) )
632    pop-> f
633    (Vec .default) [ pop-> e pop-> acc
634      acc e f .call [ pop-> x pop-> acc2 acc2 x .push ] .fold
635    ] .fold ;
636  # si[impl stdlib.iter.chunks-n]
637  ## Vec-specific chunks-n: Pair(completed_chunks, current_chunk)
638  ## accumulator; finaliser flushes any non-empty trailing chunk.
639  .chunks-n ( (Vec elem) AnyInt -> (Vec (Vec elem)) )
640    pop-> n
641    (Vec .default) (Vec .default) Pair [ pop-> e pop-> acc
642      acc .a pop-> chunks
643      acc .b pop-> current
644      current e .push pop-> current
645      current .len n = :if
646        chunks current .push (Vec .default) Pair
647      :else
648        chunks current Pair
649      :end
650    ] .fold
651    pop-> final
652    final .a pop-> chunks
653    final .b pop-> current
654    current .len 0 > :if
655      chunks current .push
656    :else
657      chunks
658    :end ;
659  # si[impl stdlib.iter.unzip]
660  ## Vec-specific unzip: each element's `.a` / `.b` go onto matching Vecs.
661  .unzip ( (Vec (Pair a b)) -> (Pair (Vec a) (Vec b)) )
662    (Vec .default) (Vec .default) Pair [ pop-> e pop-> acc
663      acc .a pop-> aa
664      acc .b pop-> bb
665      aa e .a .push
666      bb e .b .push
667      Pair
668    ] .fold ;
669:end
670
671:impl Foldable (HashMap key val)
672  .fold ( (HashMap key val) acc [acc (Pair key val) -> acc] -> acc )
673    pop-> f pop-> acc pop-> map 0 pop-> i
674    :loop i map .len = :if acc :ret :end
675      acc i map hashmap-entry-at Pair f .call pop-> acc
676      i 1 + pop-> i
677    :end ;
678  .for-each ( (HashMap key val) [(Pair key val) ->] -> )
679    pop-> f pop-> map 0 pop-> i
680    :loop i map .len = :if :ret :end
681      i map hashmap-entry-at Pair f .call
682      i 1 + pop-> i
683    :end ;
684:end
685
686:impl Foldable (HashSet elem)
687  .fold ( (HashSet elem) acc [acc elem -> acc] -> acc )
688    pop-> f pop-> acc pop-> set 0 pop-> i
689    :loop i set .len = :if acc :ret :end
690      acc i set hashset-entry-at f .call pop-> acc
691      i 1 + pop-> i
692    :end ;
693  .for-each ( (HashSet elem) [elem ->] -> )
694    pop-> f pop-> set 0 pop-> i
695    :loop i set .len = :if :ret :end
696      i set hashset-entry-at f .call
697      i 1 + pop-> i
698    :end ;
699:end
700
701# si[impl coll.range.foldable]
702:impl Foldable (RangeBoth a b)
703  .fold ( (RangeBoth AnyInt AnyInt) acc [acc AnyInt -> acc] -> acc )
704    range-fold ;
705  .for-each ( (RangeBoth AnyInt AnyInt) [AnyInt ->] -> )
706    range-for-each ;
707:end
708
709# si[impl coll.mappable]
710## Trait for collections whose elements can be transformed element-wise.
711## The `mapped` associated type determines the output collection so that
712## length-preserving maps over `Vec n` can preserve `n` while maps over
713## `HashSet` fall back to a `Vec`.
714:trait(pub) Mappable | mapped
715  ## Apply `f` to each element, collecting results into `(mapped b)`.
716  ## ( (Self a) [a -> b] -> (mapped b) )
717  .map ( (Self a) [a -> b] -> (mapped b) )
718:end
719
720:impl Mappable (Vec a len) | (Vec b len)
721  .map ( (Vec a len) [a -> b] -> (Vec b len) )
722    pop-> f pop-> vec (Vec .default) pop-> out 0 pop-> i
723    :loop i vec .len = :if out :ret :end
724      i vec .get f .call out swap .push pop-> out
725      i 1 + pop-> i
726    :end ;
727:end
728
729# si[impl coll.filterable]
730## Trait for collections that support element selection by predicate.
731## The `filtered` associated type determines the output collection so
732## that `HashSet` filters return a `HashSet` while `Vec` filters return
733## a length-existential `Vec _`.
734:trait(pub) Filterable | filtered
735  ## Retain only elements for which `pred` returns `true`.
736  ## ( (Self elem) [elem -> Bool] -> filtered )
737  .filter ( (Self elem) [elem -> Bool] -> filtered )
738:end
739
740:impl Filterable (Vec elem len) | (Vec elem len)
741  .filter ( (Vec elem len) [elem -> Bool] -> (Vec elem len) )
742    pop-> pred pop-> vec (Vec .default) pop-> out 0 pop-> i
743    :loop i vec .len = :if out :ret :end
744      i vec .get pop-> e
745      e pred .call :if out e .push :else out :end pop-> out
746      i 1 + pop-> i
747    :end ;
748:end
749
750# si[impl coll.keyed]
751## Trait for collections that support key-indexed access.
752## Independent of iteration order — does not require `Foldable`.
753:trait(pub) Keyed
754  ## Return `Some val` if `key` is present, `None` otherwise.
755  ## ( key (Self key val) -> (Option val) )
756  .lookup ( key (Self key val) -> (Option val) )
757  ## Return `true` if `key` is present in the collection.
758  ## ( key (Self key val) -> Bool )
759  .contains-key ( key (Self key val) -> Bool )
760:end
761
762:impl Keyed (HashMap key val)
763  .lookup ( key (HashMap key val) -> (Option val) )
764    .get :if Some :else drop None :end ;
765  .contains-key ( key (HashMap key val) -> Bool )
766    .get swap drop ;
767:end
768
769# si[impl coll.chainable]
770## Trait for collections that can be concatenated end-to-end.
771:trait(pub) Chainable
772  ## Produce a single collection containing every element of the first
773  ## followed by every element of the second, in iteration order.
774  ## ( (Self elem) (Self elem) -> (Self elem) )
775  .chain ( (Self elem) (Self elem) -> (Self elem) )
776:end
777
778:impl Chainable (Vec elem len)
779  .chain ( (Vec elem len) (Vec elem len) -> (Vec elem len) )
780    pop-> v2 pop-> v1 v1 pop-> out 0 pop-> i
781    :loop i v2 .len = :if out :ret :end
782      out i v2 .get .push pop-> out
783      i 1 + pop-> i
784    :end ;
785:end
786
787# si[impl coll.indexed]
788## Trait for collections with positional access by integer index.
789:trait(pub) Indexed
790  ## Return `Some elem` at zero-based index `i`, or `None` if `i` is out
791  ## of bounds.
792  ## ( AnyInt (Self elem) -> (Option elem) )
793  .at ( AnyInt (Self elem) -> (Option elem) )
794  ## Return the number of elements in the collection.
795  ## ( (Self elem) -> AnyInt )
796  .size ( (Self elem) -> AnyInt )
797:end
798
799:impl Indexed (Vec elem len)
800  .at ( AnyInt (Vec elem len) -> (Option elem) )
801    pop-> vec pop-> i
802    i 0 < :if None :ret :end
803    i vec .len ≤ not :if None :ret :end
804    i vec .get Some ;
805  .size ( (Vec elem len) -> AnyInt ) .len ;
806:end
807
808# si[impl coll.zippable]
809## Trait for collections that can be combined element-wise.
810:trait(pub) Zippable
811  ## Pair elements positionally; the result has the length of the
812  ## shorter input.
813  ## ( (Self a) (Self b) -> (Self (Pair a b)) )
814  .zip ( (Self a) (Self b) -> (Self (Pair a b)) )
815:end
816
817:impl Zippable (Vec a la)
818  .zip ( (Vec a la) (Vec b lb) -> (Vec (Pair a b) lc) )
819    pop-> vb pop-> va
820    va .len vb .len < :if va .len :else vb .len :end pop-> n
821    (Vec .default) pop-> out 0 pop-> i
822    :loop i n = :if out :ret :end
823      i va .get i vb .get Pair out swap .push pop-> out
824      i 1 + pop-> i
825    :end ;
826:end
827
828# Generic collection helpers —
829# `any` / `all` / `count` are available as `.any` / `.all` / `.count`
830# methods on the `Foldable` trait (default implementations at
831# si[coll.foldable.default]). Callers should use the method form;
832# the free-fn forms used to exist here as a compatibility surface and
833# were removed when WP-M3 hoisted them back into the trait-default
834# surface they duplicated.
835
836# si[impl stdlib.iter.sum+1]
837## Sum the elements of a `Foldable` collection of AnyInt values.
838## Spec targets a generic `(Add num num | num)` constraint; monomorphise
839## to AnyInt for now since the trait-constrained generic :fn path
840## doesn't specialise (Phase 1b open issue).
841## ( (f AnyInt) -> AnyInt ) { (Foldable f) }
842:fn(pub) sum-int ( (f AnyInt) -> AnyInt ) { (Foldable f) }
843  0 [ + ] .fold
844:end
845
846# si[impl stdlib.iter.product+1]
847## Multiply the elements of a `Foldable` collection of AnyInt values.
848## ( (f AnyInt) -> AnyInt ) { (Foldable f) }
849:fn(pub) product-int ( (f AnyInt) -> AnyInt ) { (Foldable f) }
850  1 [ * ] .fold
851:end
852
853# Collection trait aliases
854## Sequential-collection alias — any type that is foldable, mappable,
855## filterable, chainable, indexed, and zippable.
856:trait(pub) Seq { (Foldable Self) (Mappable Self) (Filterable Self) (Chainable Self) (Indexed Self) (Zippable Self) } :end
857## Key-value-collection alias — any keyed, foldable type.
858:trait(pub) Map { (Keyed Self) (Foldable Self) } :end
859# si[impl coll.set+1]
860## Unique-element collection trait. Requires `Foldable` + `Filterable`
861## and carries the set-algebra methods. Concrete impls (HashSet,
862## BTreeSet) supply the bodies. Unicode operator sugar (`∪`/`∩`/`∖`/
863## `△`/`⊆`/…) desugars to these calls.
864:trait(pub) Set { (Foldable Self) (Filterable Self) }
865  ## Union of two sets.
866  ## ( (Self a) (Self a) -> (Self a) )
867  .union ( (Self a) (Self a) -> (Self a) )
868  ## Intersection of two sets.
869  ## ( (Self a) (Self a) -> (Self a) )
870  .intersection ( (Self a) (Self a) -> (Self a) )
871  ## Elements in the first set not in the second.
872  ## ( (Self a) (Self a) -> (Self a) )
873  .difference ( (Self a) (Self a) -> (Self a) )
874  ## Elements in either set but not both.
875  ## ( (Self a) (Self a) -> (Self a) )
876  .symmetric-difference ( (Self a) (Self a) -> (Self a) )
877  ## `true` iff every element of the first is in the second.
878  ## ( (Self a) (Self a) -> Bool )
879  .is-subset ( (Self a) (Self a) -> Bool )
880  ## `true` iff every element of the second is in the first.
881  ## ( (Self a) (Self a) -> Bool )
882  .is-superset ( (Self a) (Self a) -> Bool )
883  ## `true` iff the two sets share no elements.
884  ## ( (Self a) (Self a) -> Bool )
885  .is-disjoint ( (Self a) (Self a) -> Bool )
886  ## `true` iff `a` is an element of the set.
887  ## ( (Self a) a -> Bool )
888  .contains ( (Self a) a -> Bool )
889:end