seq is the workhorse toolbox for the structure of
lists: test every element, find where something lives, take the first few,
stitch two lists together, and so on. It is the pile of everyday verbs you
reach for the moment you have more than one of something. None of it is
built into the language. Every word here is written in plain Shoddy on top
of a handful of built-in building blocks: Fold,
Map, Filter, and the trio
First/Rest/Prepend that take a list
apart and put it back together. The machine is pure and self-hosted.
Self-hosted means it is written in the same Shoddy you write; pure means
nothing here touches a file or the screen, so the same input always gives
the same answer. You can read the whole machine like a recipe book. (Two
things that used to live here have better homes now: totalling and averaging
belong to stats.shoddy, and sorting became the
built-in Sort, which needs no Include at all.)
The list this machine walks was invented twice in two years, a few
hundred miles apart. In 1956 Allen Newell, Cliff Shaw and Herbert Simon were
building a program to prove logic theorems. They needed a data structure
that could grow and shrink mid-computation (something no array could
do) and hit on chaining: each item holds a value and the address of
the next. John McCarthy took the idea into Lisp in 1958 and gave it its
lasting form, the two-field cons cell. Its accessors (the words that
read its two fields) are the famous car and
cdr, fossilised register names of the IBM 704 he built it
on. What made the cons cell immortal is the property this whole library
leans on: a list is either empty, or an item in front of a smaller list.
That definition is already a recursion scheme: a ready-made shape for
functions that call themselves. First, Rest, Prepend: every word in
seq is a sentence built from that three-word vocabulary.
Fold is the observation, half a century old now, that almost
all of the sentences are the same one.
Almost every program ends up juggling several values at once: a list
of scores, a row of prices, the words in a sentence, the students in a class.
The language gives you the raw ability to loop over them. But writing the
same little loop by hand every time (to count how many are over the line, to
grab the first three, to walk two lists in step) gets old fast. Every
hand-written loop is also a fresh chance at an off-by-one error, a count that
lands one too high or one too low. seq hands you those loops
already written, named, and tested. You say what you mean,
CountIf(students, passed), Taken(prices, 3),
Zip(names, scores), instead of spelling out how. It is
also the quiet foundation a great many other machines are built on. When
another machine needs to search, slice, or zip a list, it leans on
seq rather than reinventing it.
One thing worth knowing up front: Shoddy has two flavours of sequence.
The List is grown from front to back with
First/Rest/Prepend. The
Array is a fixed block you index into. Some words here are
poly: they work on either kind, because they
only ever ask a sequence to fold or map over itself. The predicates
(the testing words Any, All, CountIf
and Contains) are all poly. The rest (searching,
slicing, and pairing) are List-only. They take the
sequence apart with structural recursion (peeling off the first item and
working on the rest), and that is a List's trick, not an Array's. The Word
Reference below labels which is which.
Include the file and the words are yours. Most of them take a list as
their first argument. The ones that test each element (like Any,
All, CountIf) take a little function too,
often written inline as a Fn lambda (a small unnamed function),
or as a partially-applied operator like >(4) (read "greater
than 4": an operator with one side already filled in).
Shoddy · The MachinesInclude "seq.shoddy"
Def Main()
Let xs = { 5, 3, 8, 1, 9, 2 }
Print(CountIf(xs, >(4))) ' 3 (5, 8, 9)
Print(Any(xs, =(8))) ' True
Print(Contains(xs, 7)) ' False
Let top3 = Taken(Sort(xs), 3) ' Sort is a builtin
Each(top3, Fn(n) => Print(Str(n))) ' 1, then 2, then 3
Print(IndexOf(xs, 8)) ' 3 (8 is the 3rd item)
Let names = { "ADA", "LIN", "GRACE" }
Each(Zip(names, xs), Fn(pr) => Print(Fst(pr) & " = " & Str(Snd(pr))))
' ADA = 5, LIN = 3, GRACE = 8A few things worth remembering:
Append and Taken hand you back a brand-new list
and leave the original untouched. Chain them freely:
Taken(Sort(xs), 3) sorts a copy (with the Sort
builtin), then takes three from that.IndexOf returns
1 for the first item, and 0 when the value is not in
the list at all, a "not found" signal that at least cannot be mistaken
for a real position. IndexFrom does the same but lets you start
the search partway along. IndexOpt asks the same question and
answers it in the language rather than in a number you have to remember:
Some(3) or None.Last reaches for a final element, so an empty list has no
sensible answer to give it.Zip and
ZipWith pair items up position by position and stop when either
list runs out: three names against six numbers gives three pairs, as
in the example.Because it is the common vocabulary of lists, seq shows up
underneath a lot of other machines. Anywhere a machine needs to
search, filter, or slice, it tends to Include this one rather
than roll its own.
The twenty-two sequence and higher-order words the runtime dispatches: not defined here, documented here
These are not seq's Defs. The engine dispatches
them (runs them itself) and a Def whose name is a
builtin is refused. They are listed on this page because seq is
the sequences machine and everything it declares is written over them. They
need no Include. The same twenty-two are documented in
machines/seq.shoddy's own header block.
Two sequence kinds. A List is the
recursive kind: a chain of cells that First and
Rest take apart front to back, O(1) each with nothing copied,
and that Nth indexes in O(1) after its first call. An
Array is the indexed kind: fixed length, Nth in
O(1) from the start, and SetNth answers a new array by copying
the whole of it, where SetNth on a list rebuilds only the cells
before the change. ToArray and ToList convert.
Everything here counts from 1, and all twenty-two are pure, including
SetNth, which answers a new sequence and leaves the
original alone.
| Word | Description |
|---|---|
| Map(xs, f) | Every element through f. Poly: an
array maps to an array. |
| Filter(xs, p) | The elements p answers True for, in
order. |
| Fold(xs, init, f) | A fold from the left: the accumulator (the
running result) starts at init and f sees it first. Almost
every word in the reference below is Fold underneath. |
| Each(xs, f) | f applied to every element for its
effect, answering nothing. The one word in this group that exists
only for impure work. |
| Times(n, f) | f applied to 1, 2, … n,
for effect. The counted loop. |
| Range(lo, hi) | The whole numbers from lo to
hi inclusive. An empty list when hi is below
lo, so a loop over an empty range does nothing. |
| Word | Description |
|---|---|
| Length(xs) | How many elements. List and array
only: it refuses a string outright, which is why
str's Len is a separate word and not a
near miss for this one. |
| IsEmpty(xs) | Whether it holds nothing. |
| First(xs) | The first element. Aborts on an empty sequence. |
| Rest(xs) | Everything after the first: the tail cell itself, shared, in O(1). Lists only: on an array it would have to copy. |
| Nth(xs, k) | The k-th element, counting from 1.
Aborts outside the range. O(1) on an array, and on a list after the first
call, which builds the list's index. |
| Word | Description |
|---|---|
| Prepend(v, xs) | xs with v on the
front. Lists only, and O(1): one new cell, the rest shared.
This is the pair to First/Rest that structural
recursion is written with. |
| SetNth(xs, k, v) | A sequence with its k-th element
replaced. The original is unchanged. Aborts outside the
range. |
| Reverse(xs) | The same elements, back to front. |
| Concat(xs, ys) | The two joined. Append and
Flatten below are written over it. |
| Sort(xs) | Ascending, over all-numbers or all-strings. Mixed kinds have no order and are refused. It is a sequence operation and so it is documented here, though stats is its heaviest caller: every median, quantile and rank goes through it. |
| Dim(n, init) | An Array of n copies
of init. The way an array is made, since there is no array
literal. |
| ToArray(xs) / ToList(arr) | Between the two kinds. An array is
for Dim-shaped data and for SetNth by copy;
indexing a list needs no conversion. |
| Taken(xs, n) | The first n elements; the whole list
when n reaches its length, an empty one when n is 0
or below. Lists only. |
| DropN(xs, n) | Everything after the first n:
xs itself when n is 0 or below, an empty list past
the end. Lists only. Nothing is copied; the answer is a cell
of xs. |
| ZipWith(xs, ys, f) | f over the pairs, stopping at
the shorter. Poly in what it is handed, a list in what it answers;
Zip below is this with Pair. These three were
Defs here until lists became cons cells. |
Every word, plus the Pair type
| Word | Description |
|---|---|
| Any(xs, p) | True if the test p holds for at least
one item in xs. False for an empty list. |
| All(xs, p) | True if the test p holds for every
item in xs. True for an empty list (nothing fails it). |
| CountIf(xs, p) | How many items in xs pass the
test p. |
| Contains(xs, v) | True if the value v appears
somewhere in xs. |
| Word | Description |
|---|---|
| IndexOf(xs, v) | The 1-based position of the first
v in xs, or 0 if it is not
there. |
| IndexFrom(xs, v, k) | Like IndexOf, but treats the
front of xs as position k: the building
block IndexOf is written on, useful directly when you want to
number from something other than 1. |
| IndexOpt(xs, v) | The same search, returning
Some(position) or None. The clearer form, and the
one to reach for in new code; Option is the language's, so
matching on it needs no further Include. IndexOf
keeps its 0 because too much already reads it. |
| Word | Description |
|---|---|
| Append(xs, x) | A new list that is xs with
x tacked on the end. |
| Last(xs) | The final item of xs. Needs a
non-empty list. |
| Flatten(xss) | Takes a list of lists and joins them end to end into one flat list. |
| Word | Description |
|---|---|
| Pair | A two-value bundle with fields Fst and
Snd: what Zip hands back for each matched-up
couple. |
| Zip(xs, ys) | Pairs up xs and ys
position by position into a list of Pairs, stopping when the
shorter list runs out: the ZipWith builtin with Pair
as the combiner. |
| User | How | |
|---|---|---|
 | alg | Flatten is the whole of expansion and variable collection, All and Any carry the invariants, Append builds the coefficient lists, and IndexOf looks up a binding. |
 | bool | CountIf is BoolPopCount and scores the greedy cover, Contains and Append dedupe the implicant sets by value, Flatten collects each combining round, and All/Any carry the tautology and coverage tests. |
 | csv | Zip pairs a row with its header, IndexOf finds a
named column, and All and Append carry the scanner. |
 | cuttle | Pair carries a stack cell's record case, and the list plumbing implements the stack and its shuffles. |
 | demographics | Taken
previews the loaded rows in the trainer. |
 | devils-dust | All
compares knob settings, CountIf takes the wool census,
Taken caps the wisp trails. |
 | dict | Any
answers the has-key question over the pair list. |
 | eng | Append builds the prime-factor and quotient lists, CountIf is Euler's totient, and ZipWith is the dot product. |
 | fin | Flatten expands a cash-flow list; Taken walks the
running cash position. |
 | geo | Last, Taken and DropN close a polygon
and split a coordinate's numbers; Pair carries the furthest
candidate through the Douglas–Peucker search. |
 | halifax | Contains reads the shell-word tables, DropN takes the last rows for the tape pane, and Append builds the lines a turn shows. |
 | html | Contains tests a tag against the void and raw-text sets. |
 | https | Append accumulates the reply as fragments, so a drained body
is joined once rather than copied per chunk. |
 | invaders | Any
asks the fleet questions: anyone left, anyone hit? |
 | iris | Taken
previews the data, ZipWith pairs truth with prediction for the
confusion matrix. |
 | json | Zip pairs keys with values, and All checks a document
before it is written. |
 | lin | Append accumulates the characteristic polynomial's coefficients and the eigenvalues a scan finds; DropN trims the leading term. |
 | matrix | Flatten
and ZipWith build matrices from rows and stitch vectors
together. |
 | mip | Any checks the integer list against the variables that exist. |
 | mps | Contains tests a row name against the sections already seen, and IndexOf turns a name into the column it stands for. |
 | mungo-caverns | Contains
in fourteen files (vocabulary, inventory and state are all list
membership) plus Append, Any, All,
Flatten, Last and CountIf. |
 | neural | ZipWith walks a layer's weights against its inputs. |
 | pac-vt100 | Any,
Contains and Flatten: the maze and ghost
questions. |
 | plotter | Zip pairs the series, Taken trims it to the axis,
and Any and CountIf decide the ticks. |
 | reckoner | List plumbing throughout the tokenizer, the evaluator's walk, and the combinators' folding. |
 | scribbler | List
chores in the event layer (Last). |
 | shaker | Pair
carries the two halves of a Feistel block; All and
Last check the field and read the tag. |
 | simplex-from-mps | Contains
reads the command-line flags. |
 | sparky | Filter and Length count the words a sparky session has defined, for its load report. |
 | sinq | Pair carries a decorated element through the sort, Contains is what the set words ask, and Append, Last and Flatten do the rest. seq is the only machine sinq stands on, which is what lets anything take sinq without dragging a tree in behind it. |
 | sparse | All checks a column's shape, Flatten gathers its entries, and Pair holds them while they are sorted into columns. |
 | stats | CountIf,
Flatten and ZipWith under the summaries. |
 | tally | Contains, Append, Flatten and Zip thread through the derive, filter and report stages. |
| weather-glass | Taken cuts the feed to 72
hours, and the render accumulates its lines with Prepend. |
 | xml | Zip and Append build the attribute list;
Any and All walk the tree. |
None. seq is the trunk. It stands on the list builtins alone, which is why half the library can lean on it without dragging anything else in.