sequences

chapter 02 handed you the list verbs and chapter 05 gave you the pipe to chain them. this chapter is about what a chain actually is. the short version: list/map does not return a list, consumers do all the work, and the work happens one element at a time. everything else on this page falls out of those three facts.

a recipe, not a result

bind an adapter's result to a name and print it, and the value tells you what it is:

import "std/list"

xs = [1 2 3]
recipe = list/map xs (n -> n * 10)

print "the recipe: {recipe}"
>> print "the result: {list/to_list recipe}"

the recipe: list/mapped <fn> list/cursor 1 [1 2 3]
the result: [10 20 30]

the first print shows a small record—an arm holding your function and a cursor over the source—that describes the mapping without performing it. no multiplication has happened yet. chapter 05's io values describe an effect the executor performs later, and an adapter describes a traversal a consumer performs later. list/to_list is the consumer that realizes the recipe into an ordinary list, and it is the usual last step before printing.

the shapes the recipe is made of—the cursor, the arms—belong to std/list's own machinery. you will see them in rendered output and can otherwise leave them alone.

pull, one element at a time

because an adapter is a recipe, composing adapters costs nothing, and the source can be infinite. list/naturals counts 1, 2, 3, … forever; nothing about writing it down runs forever, because nothing runs at all until a consumer pulls:

import "std/list"

pub play =
  firsts = list/to_list (list/take list/naturals 5)
  squares = list/map list/naturals (n -> n * n)
  print "{firsts}"
  >> print "{list/to_list (list/take squares 4)}"

[1 2 3 4 5]
[1 4 9 16]

when to_list pulls, each element flows through the whole chain before the next is touched: the fourth natural is squared and delivered, then the pull stops, because take said four. no intermediate list of squares ever exists; the recipe was asked four times. an unbounded consumer on an unbounded generator is a program that runs forever, which in kanso is a legal thing to write; take is how you say where the end is.

consumers stop at the answer

some consumers do not need the whole sequence, and they do not take it. find, all?, and any? pull until the answer is settled and return on the spot:

import "std/list"

pub play =
  found = list/find list/naturals (n -> n * n > 50)
  any_big = list/any? list/naturals (n -> n > 3)
  print "{found} {any_big}"

8 true

both lines consume naturals, and both programs finish. find squared eight numbers, saw 64 clear the bar, and stopped; any? stopped at 4. a predicate that is never satisfied over an infinite source still runs forever—the language cannot know your predicate's future—but a satisfiable question over an infinite sequence is answered in finite time.

maps out of sequences

a family of consumers builds maps instead of scalars. tally counts occurrences; group_by files each element under a key of your choosing:

import "std/list"

orders = ["oat" "soy" "oat" "whole" "oat"]

pub play =
  print "tally {list/tally orders}"
  >> print "letters {list/group_by orders (s -> s[1])}"

tally { "oat":3 "soy":1 "whole":1 }
letters { "o":["oat" "oat" "oat"] "s":["soy"] "w":["whole"] }

index_by and to_h round out the family, and all four share one collision rule: when two elements land on the same key, the last write wins—the same rule put follows, so a map built by a consumer behaves like the map you would have built by hand.

the chain compiles to one loop

chapter 10 introduced the counters. point them at a chain:

import "std/list"

fn build 0 acc
  acc

fn build n acc
  build (n - 1) (push acc n)

pub play =
  xs = build 1000 []
  tripled = list/map xs (n -> n * 3)
  big = list/select tripled (n -> n > 150)
  print "kept {list/sum big}"

allocs=12
alloc_bytes=43936
arena_blocks=1
arena_peak_bytes=1048576
cohort_frees=0
cohort_kept=0
perm_allocs=1
beat_iters=1000
evac_allocs=0
evac_bytes=0
put_mut_fast=0
put_mut_grow=0
push_mut_fast=0
push_mut_slow=1000
thunk_allocs=0
thunk_forces=0
thunk_evals=0
thunk_frees=0
thunk_escaped=0
thunk_live_exit=0
el_parses=0
ryu_renders=0
utf8_bytes=0
find2_calls=0
append_fast=0
append_grow=0
utf8_zerocopy=0
carry_dedup=0
bytes_malloc=0
bytes_freed=0
str_scans=0
str_scan_bytes=0
buf_reuse=0
held_peak_bytes=0
view_allocs=0
view_frees=0
sh_str=64
sh_rec=0
sh_buf=0
sh_map=0
sh_bytes=0
kept 1497675

twelve allocations, and the building of the thousand-element source accounts for them. the map, the select, and the sum together added zero—the compiler fused the chain into one flat loop whose body multiplies, tests, and adds, with no recipe records and no per-element machinery at all. the pipe spelling of the same chain fuses identically. laziness is the semantics; fusion is the compiler noticing that a chain consumed on the spot never needs the recipe to exist.

what to remember

• an adapter (map, select, reject, take, drop, zip) returns a recipe, not a list. a consumer forces it.
• elements flow one at a time through the whole chain. no intermediate collections exist.
• generators (naturals, repeat, cycle, iterate) are infinite; consumers bound them. find, all?, and any? stop at the answer.
• the map builders (tally, group_by, index_by, to_h) resolve key collisions the way put does: last write wins.
• list/to_list realizes a recipe. reach for it when a chain's result needs to be a plain list—usually right before printing.
• a chain ending in a consumer fuses into one flat loop, spelled with pipes or nested. the counters can prove it to you.

exercises

1. build a two-stage recipe—a select over a map—bind it, and predict what the print will show before you run it. check your prediction against the rendered value, and find both of your functions in it.
2. using only list/find and list/naturals, compute the first triangular number greater than 100. (the nth triangular number is n * (n + 1) / 2.) confirm the program terminates, and explain in one sentence why it must.
3. change fused.kso's loop count from 1000 to 2000 and rerun under KANSO_COUNTERS=1. from the two allocs readings, work out how much of the cost belongs to building the source and how much to the chain.
4. group_by and index_by take the same arguments. run both over the same list with a key function that sends every element to one key, and explain the two results using the collision rule each follows.