tur/list
typed singly-linked List[A] with Cons cells.
Typed singly-linked list. List[A] = Option[Cons[A]]. At runtime, nil is 0 and a cons cell specializes its head slot for concrete A; the tail link is the recursive occurrence (Cons A) -- a typed pointer to the next cell, NULL for the end -- so .tail hands back a (Cons A) and a walk needs no per-step ascription. The carrier-level helpers (list-head, list-tail, list-length, ...) still read the same two-word cell through the :int carrier, which a (Cons A) coerces to in argument position.
Since: Phase TC1-B
Cons
(defstruct Cons :heap [A] (head A) (tail (Cons A)))
parameterized cons cell with typed head and tail.
Since: Phase TC1
tcons
(tcons [A])
prepend a value to a typed list.
Element-generic: the head slot specializes to A's concrete C layout, so a float head builds a double-headed cell -- matching what (list ...) and tcons-of produce. Builds the cell with make-struct Cons (the same body as tcons-of) rather than an int-only inline-C builder, so (tcons 1.5 (tnil)) type-checks just like (list 1.5 ...) does.
| h | head element of type A | |
| t | tail list as the :int carrier (another typed list, which coerces | |
| to the carrier, a carrier-level list, or tnil) |
A new (Cons A) cell with h at the front. The head slot is laid out as A's
concrete C type (e.g. a double field for a float head), exactly like
tcons-of. A (Cons A) carrier coerces to the :int carrier in argument
position, so the result still composes with the list-head/list-tail
walkers and the carrier-level list helpers (nest (tcons x (tcons ...))
just like before). This is the carrier-level constructor -- the tail
arrives as the :int word the carrier helpers produce and is ascribed
to (Cons A) here; tcons-of is the typed-tail twin.
(tcons 1 (tcons 2 (tnil))) ; => (Cons int) [1, 2] (tcons 1.5 (tnil)) ; => (Cons float) double-headed cell
Since: Phase TC1
tcons-of
(tcons-of [A])
typed Cons[A] constructor with a typed head slot.
| h | head element of type A | |
| t | tail link, a (Cons A) (another cell, or (tnil) for the end) |
A (Cons A) value whose head field is laid out as the concrete C type
for A (e.g. double for :float), with no user-side bit-cast, and
whose tail is the typed link.
(let [c (tcons-of 1.5 (tnil))] (.head c)) ; => 1.5, read as a `double` field
Since: Phase TS3
tnil
(tnil [A])
return an empty typed list.
The empty (Cons A): the NULL link. Its element type is taken from the
context -- (tcons-of 1 (tnil)) pins A to int -- and it coerces to the
:int carrier 0 wherever a carrier-level list is expected.
(tnil) ; => empty list
Since: Phase TC1
tnil?
(tnil? [A])
check whether a typed list is empty.
Takes the typed list, so a Saffron any holding a cons list seams into it (the target grounds to (Cons any), which is what the box carries). For a carrier-level :int list use null?, its :int-taking twin.
| l | List[A], a (Cons A) |
true if l is the empty list, false otherwise.
(tnil? (tnil)) ; => true (tnil? (tcons 1 (tnil))) ; => false
Since: Phase TC1
thead
(thead [A])
return the head element of a non-empty typed list.
| l | Cons[A] |
The head element of type A.
(let [l (:: (make-struct Cons 42 (tnil)) (Cons int))] (thead l)) ; => 42
Since: Phase TC1
ttail
(ttail [A])
return the tail of a non-empty typed list.
| l | Cons[A] |
The tail list, a (Cons A) -- the NULL link (carrier 0) after the last
cell. It coerces to the :int carrier in argument position, so
(tnil? (ttail l)) and the carrier-level helpers still take it.
(let [l (:: (make-struct Cons 1 (tnil)) (Cons int))] (tnil? (ttail l))) ; => true
Since: Phase TC1
tlength-acc__
(tlength-acc__ [A])
internal: tail-recursive count behind tlength.
tlength
(tlength [A])
count the elements of a typed (Cons A) list.
The element-aware sibling of list-length. Where list-length walks the chain as a fixed carrier struct { int64_t head; int64_t tail; }, tlength reads (.tail xs) at the concrete (Cons A) layout, so it stays correct when A is a by-value aggregate (e.g. (Option int)) whose head pushes the tail link past offset 8 -- the carrier walk segfaults there, this does not. The same holds for an any element, whose head is a two-word tagged value: a call to list-length / length on such a list is elaborated as a call to tlength (list-length-on-cons-any-segfaults). The walk is tail-recursive, so a long list costs no stack.
| xs | the (Cons A) list to measure |
Integer length.
(tlength (:: (list (some 1) (some 2)) (Cons (Option int)))) ; => 2
Since: Phase G4 (carrier<->concrete ABI crossing audit)
list-length
(list-length [l :int])
count the number of elements in a typed list.
Walks the carrier cell { int64_t head; int64_t tail; }. A (Cons A) whose head is wider than that word -- an any element (every Saffron list) or an inline by-value aggregate -- is counted by tlength instead: the call is elaborated as (tlength l), and likewise length, list-head/car and list-tail/cdr for their typed twins.
| l | List[A] |
Integer length.
(list-length (list 1 2)) ; => 2
Since: Phase TC1
list-eq?
(list-eq? [l1 :int l2 :int ^fat cmp-fn :(fn [int int] bool)] :bool)
compare two typed lists element-wise.
| l1 | first List[A] | |
| l2 | second List[A] | |
| cmp-fn | comparator fn [a :int b :int] :bool |
true if both lists have the same elements in the same order.
(list-eq? (list 1) (list 1) (fn [a b] (= a b))) ; => true
Since: Phase TC1
cons-eq-go
(cons-eq-go [A])
by-value structural equality walk over two non-nil (Cons A) cells.
Path A helper for Eq [Cons]: receives the two head cells by value, compares heads through (Eq A), then recurses on the tails -- recovering a typed (Cons A) view of each :int tail link via ascription, mirroring the tlength walk. No inline-C, no int64-carrier comparator: the per-instance spec emits a clean by-value bool (...)(Cons__A *, Cons__A *) body. Callers must guard the nil (0) case first -- this helper dereferences .head/.tail and assumes both cells are present.
| c1 | first head cell, a non-nil (Cons A) | |
| c2 | second head cell, a non-nil (Cons A) |
true when both chains have equal heads in the same order and equal length.
(cons-eq-go (:: (tcons 1 (tnil)) (Cons int))
(:: (tcons 1 (tnil)) (Cons int))) ; => true
Since: Phase TCE (typed-collection-eq-consumers)
Eq[Cons]
(definstance Eq [Cons])
element-wise equality using the element type's Eq instance.
tur-list-homog__
(tur-list-homog__ [A])
internal: compile-time element homogeneity check.
Both parameters share the single type variable A, so a call with two differently-typed arguments is a TUR-E0001 at elaboration. The body is a no-op; the call exists only to make the type-checker enforce that adjacent (list ...) elements have the same type. No allocation (fixed arity).
list-homog-chain__
(list-homog-chain__ [& xs])
internal: pairwise-chain tur-list-homog__ over xs.
Emits (tur-list-homog__ x0 x1), (tur-list-homog__ x1 x2), ... so all elements transitively unify to one type. Zero or one element: no check.
list-build__
(list-build__ [& xs])
internal: right-fold xs into a typed (tcons-of ...) chain.
Routes through the polymorphic-head constructor tcons-of (not the int-only tcons), so the resulting cons cells specialize their head slot to the element type A (e.g. a double field for :float). The homogeneity check runs separately in the list macro, so this just builds the chain.
list
(list [& xs])
construct a typed list from N values via nested tcons-of.
| & xs -- zero or more values, all of a single element type A. |
The right-folded (tcons-of ... (tnil)) chain, typed as (Cons A) where A
is the element type recovered from the literal -- so (list 7.1 2.5) is a
(Cons float) whose head slot is a double, and (list 1 2 3) is a
(Cons int). A (Cons A) carrier coerces to :int in argument position, so
the result still composes with list-length, list-eq?, and the rest of the
:int-taking carrier API; an empty (list) is the bare :int carrier 0.
(list) ; => (tnil), carrier 0 (list 1 2 3) ; => (Cons int): tcons-of 1 (tcons-of 2 (tcons-of 3 (tnil))) (list 7.1 2.5) ; => (Cons float): a double-headed cons chain ; Heterogeneous -- type error: ; (list 1 "x") ; => TUR-E0001: expected int, got cstr; use tuple2 instead
Note: all elements must unify to a single type. Mixing types -- e.g.
(list 1 "x" 3.14) -- is a type error (TUR-E0001 on the offending element). That genuinely-heterogeneous case is the one place to reach for tuple2, tuple3, tuple4, or tuple5 instead; a homogeneous non-int list (like a float list) is exactly what this macro now builds directly.
Since: List literal macro
list*
(list* [& args])
prepend values onto an existing list tail.
| & args -- one or more arguments; the last is the existing tail list, | ||
| prior arguments are prepended left-to-right. |
The right-folded (tcons-of ... tail) chain where tail is the last argument. With a single argument, returns it unchanged (identity on the tail). Routing through the polymorphic-head tcons-of means a non-int prefix (e.g. a float) specializes its head slot, mirroring (list ...).
(list* (tnil)) ; => (tnil) (list* 1 2 (tnil)) ; => (tcons-of 1 (tcons-of 2 (tnil))) (list* 1 2 (list 3 4)) ; => (Cons int) of 1 2 3 4 (list* 7.1 (list 2.5)) ; => (Cons float) of 7.1 2.5
Note: each prefix element pins its own cons cell's head type; the prefix
elements should share the tail's element type. A (Cons A) tail coerces to the :int tail carrier, so the chain composes with the carrier list API. For genuinely heterogeneous needs, use tupleN.
Since: List literal macro
list-head
(list-head [l :int] :int)
head element of a non-empty carrier-level list.
list-tail
(list-tail [l :int] :int)
tail pointer of a non-empty carrier-level list.
list-concat
(list-concat [l1 :int l2 :int] :int)
concatenate two lists.
| l1 | first List[A] | |
| l2 | second List[A] |
A new list with all elements of l1 followed by all elements of l2. Returns l2 directly when l1 is empty (no allocation).
(list-concat (list) (list 1 2)) ; => (list 1 2) (list-concat (list 1 2) (list)) ; => (list 1 2) (list-concat (list 1 2) (list 3 4)) ; => (list 1 2 3 4)
Note: l1 and l2 elements must share the same type (all :int at carrier
level). An empty l1 returns l2 directly (no allocation). This function is a prerequisite for unquote-splicing in list-quasiquote-plan.md; the N-ary signature should be preserved.
Since: List literal macro
car
(car [l :int] :int)
head of a cons-built list (classic-Lisp alias for list-head).
Pairs with the surviving cons builtin so the classic constructor + destructor surface is whole: build with cons, take apart with car/cdr.
| l | a non-empty carrier-level list (e.g. built with cons or list) |
The head element (carrier :int).
(car (cons 11 (cons 22 (tnil)))) ; => 11
Since: Phase TC1
cdr
(cdr [l :int] :int)
tail of a cons-built list (classic-Lisp alias for list-tail).
| l | a non-empty carrier-level list (e.g. built with cons or list) |
The tail list (carrier :int; 0 when l had a single element).
(car (cdr (cons 11 (cons 22 (tnil))))) ; => 22
Since: Phase TC1
null?
(null? [l :int] :bool)
test a cons-built list for emptiness (the :int-taking twin of tnil?).
| l | a carrier-level list (a (Cons A) coerces to it in argument position) |
true when l is the empty list, false otherwise.
(null? (tnil)) ; => true (null? (cons 1 (tnil))) ; => false
Since: Phase TC1
length
(length [l :int] :int)
count the elements of a cons-built list (alias for list-length).
| l | a carrier-level list |
Integer length.
(length (list 1 2 3)) ; => 3
Since: Phase TC1
Internal definitions
__cons-fmap-- apply a typed thunk to every head element of a Cons list.