Next: , Previous: Control, Up: Top

## 7 Pairs and lists

A pair is an object that refers to two other objects, called its car and cdr. The Kernel data type pair is encapsulated.

The null data type consists of a single immutable value, called nil or the empty list and having external representation `()`, with or without whitespace between the parentheses. It is immutable, and the null type is encapsulated.

If `a` and `d` are external representations of respectively the car and cdr of a pair `p`, then `(a . d)` is an external representation of `p`. If the cdr of `p` is nil, then `(a)` is also an external representation of `p`. If the cdr of `p` is a pair `p2`, and `(r)` is an external representation of `p2`, then `(a r)` is an external representation of `p`. When a pair is output (as by write), an external representation with the fewest parentheses is used; in the case of a finite list, only one set of parentheses is required beyond those used in representing the elements of the list. For example, an object with external representation `(1 . (2 . (3 . ())))` would be output using, modulo whitespace, external representation `(1 2 3)`.

— Applicative: pair? (pair? . objects)

The primitive type predicate for type pair. `pair?` returns true iff all the objects in `objects` are of type pair.

— Applicative: null? (null? . objects)

The primitive type predicate for type null. `null?` returns true iff all the objects in `objects` are of type null.

— Applicative: immutable-pair? (immutable-pair? objects)
— Applicative: mutable-pair? (mutable-pair? objects)

The primitive type predicates for types immutable pair and mutable pair. These return true iff all the objects in `objects` are of type immutable pair or mutable pair respectively.

SOURCE NOTE: these aren't provided in the Kernel report, but added for convenience. These can be implemented in standard kernel by using guards.

— Applicative: cons (cons object1 object2)

A new mutable pair object is constructed and returned, whose car and cdr referents are respectively `object1` and `object2`. No two objects returned by different calls to cons are `eq?` to each other.

— Applicative: set-car! (set-car! pair object)
— Applicative: set-cdr! (set-cdr! pair object)

`pair` should be a mutable pair.

These applicatives set the referent of, respectively, the car reference or the cdr reference of `pair` to `object`. The result of the expression is inert.

— Applicative: copy-es-immutable! (copy-es-immutable object)

The short description of this applicative is that it returns an object `equal?` to `object` with an immutable evaluation structure. The “-es-” in the name is short for “evaluation structure”.

The evaluation structure of an object `o` is defined to be the set of all pairs that can be reached by following chains of references from `o` without ever passing through a non-pair object. The evaluation structure of a non-pair object is empty.

If `object` is not a pair, the applicative returns `object`. Otherwise (if `object` is a pair), the applicative returns an immutable pair whose car and cdr would be suitable results for `(copy-es-immutable (car object))` and ```(copy-es-immutable (cdr object))```, respectively. Further, the evaluation structure of the returned value is isomorphic to that of `object` at the time of copying, with corresponding non-pair referents being `eq?`.

NOTE: In Kernel it's undefined whether immutable pairs are copied or left “as is” in the result. klisp doesn't copy immutable pairs, but that behaviour should not be depended upon.

— Applicative: list (list . objects)

The `list` applicative returns `objects`.

The underlying operative of `list` returns its undifferentiated operand tree, regardless of whether that tree is or is not a list.

— Applicative: list* (list* . objects)

`objects` should be a finite nonempty list of arguments.

The following equivalences hold:

```          (list* arg1) == arg1
(list* arg1 arg2 . args) == (cons arg1 (list* arg2 . args))
```
— Applicative: car (car pair)
— Applicative: cdr (cdr pair)

These applicatives return, respectively, the car and cdr of `pair`.

— Applicative: caar (caar pair)
— Applicative: cdar (cdar pair)
— Applicative: cddr (cddr pair)
— Applicative: caaar (caaar pair)
— Applicative: cdaar (cdaar pair)
— Applicative: cddar (cddar pair)
— Applicative: cdddr (cdddr pair)
— Applicative: caaaar (caaaar pair)
— Applicative: cdaaar (cdaaar pair)
— Applicative: cddaar (cddaar pair)
— Applicative: cdddar (cdddar pair)
— Applicative: cddddr (cddddr pair)

These applicatives are compositions of `car` and `cdr`, with the “a’s” and “d’s” in the same order as they would appear if all the individual “car’s” and “cdr’s” were written out in prefix order. Arbitrary compositions up to four deep are provided. There are twenty-eight of these applicatives in all.

— Applicative: make-list (make-list length [fill])

`length` shoulde be an exact non-negative integer.

Applicative `make-list` creates a new mutable acyclic list of length `length`, with all pairs having `fill` in their cars. If no value is provided for `fill`, `#inert` is used.

SOURCE NOTE: this is taken from r7rs.

— Applicative: list-copy (list-copy list)

Applicative `list-copy` creates a new mutable copy of `list`. That is, the returned list has the same list metrics as `list` and the cars in the returned list are initially `eq?` to the corresponding cars in `list`.

SOURCE NOTE: this is taken from r7rs.

— Applicative: reverse (reverse list)

`list` should be an acyclic list.

Applicative `reverse` makes a mutable copy of list but with the reverse order. That is, the returned list has the same number of pairs as `list` and the cars in the returned list are initially `eq?` to the corresponding cars in `list` but starting from the end and going backwards.

SOURCE NOTE: this is taken from r7rs.

— Applicative: get-list-metrics (get-list-metrics object)

By definition, an improper list is a data structure whose objects are its start together with all objects reachable from the start by following the cdr references of pairs, and whose internal references are just the cdr references of its pairs. Every object, of whatever type, is the start of an improper list. If the start is not a pair, the improper list consists of just that object. The acyclic prefix length of an improper list `L` is the number of pairs of `L` that a naive traversal of `L` would visit only once. The cycle length of `L` is the number of pairs of `L` that a naive traversal would visit repeatedly. Two improper lists are structurally isomorphic iff they have the same acyclic prefix length and cycle length and, if they are terminated by non-pair objects rather than by cycles, the non-pair objects have the same type. Applicative `get-list-metrics` constructs and returns a list of exact integers of the form `(p n a c)`, where `p`, `n`, `a`, and `c` are, respectively, the number of pairs in, the number of nil objects in, the acyclic prefix length of, and the cycle length of, the improper list starting with `object`. `n` is either `0` or `1`, `a + c = p`, and `n` and `c` cannot both be non-zero. If `c = 0`, the improper list is acyclic; if `n = 1`, the improper list is a finite list; if `n = c = 0`, the improper list is not a list; if ```a = c = 0```, `object` is not a pair.

— Applicative: list-tail (list-tail object k)

`object` must be the start of an improper list containing at least `k` pairs.

The `list-tail` applicative follows `k` cdr references starting from `object`.

The following equivalences hold:

```          (list-tail object 0) == object
(list-tail object (+ k 1)) == (list-tail (cdr object) k)
```
— Applicative: encycle! (encycle! object k1 k2)

The improper list starting at `object` must contain at least `k1 + k2` pairs.

If `k2 = 0`, the applicative does nothing. If `k2 > 0`, the applicative mutates the improper list starting at `object` to have acyclic prefix length `k1` and cycle length `k2`, by setting the cdr of the `(k1+k2)`th pair in the list to refer to the `(k1 + 1)`th pair in the list. The result returned by `encycle!` is inert.

— Applicative: map (map applicative . lists)

`lists` must be a nonempty list of lists; if there are two or more, they must all have the same length.

The map applicative applies `applicative` element-wise to the elements of the lists in lists (i.e., applies it to a list of the first elements of the lists, to a list of the second elements of the lists, etc.), using the dynamic environment from which map was called, and returns a list of the results, in order. The applications may be performed in any order, as long as their results occur in the resultant list in the order of their arguments in the original lists. If `lists` is a cyclic list, each argument list to which `applicative` is applied is structurally isomorphic to `lists`. If any of the elements of `lists` is a cyclic list, they all must be, or they wouldn’t all have the same length. Let `a1...an` be their acyclic prefix lengths, and `c1...cn` be their cycle lengths. The acyclic prefix length `a` of the resultant list will be the maximum of the `ak`, while the cycle length `c` of the resultant list will be the least common multiple of the `ck`. In the construction of the result, `applicative` is called exactly `a + c` times.

— Applicative: length (length object)

Applicative `length` returns the (exact) improper-list length of `object`. That is, it returns the number of consecutive cdr references that can be followed starting from `object`. If `object` is not a pair, it returns zero; if `object` is a cyclic list, it returns positive infinity.

— Applicative: list-ref (list-ref object k)

The `list-ref` applicative returns the `car` of the object obtained by following `k` cdr references starting from `object`.

NOTE: In the current report, object is required to be a list. In klisp, for now, we prefer the behaviour presented here, as it is more in line with the applicative `list-tail`. That is, we define `list-ref` by the following equivalence:

```          (list-ref object k) == (car (list-tail object k))
```
— Applicative: append (append . lists)

Here, all the elements of `lists` except the last element (if any) must be acyclic lists. The `append` applicative returns a freshly allocated list of the elements of all the specified `lists`, in order, except that if there is a last specified element of `lists`, it is not copied, but is simply referenced by the cdr of the preceding pair (if any) in the resultant list. If `lists` is cyclic, the cycle of the result list consists of just the elements of the lists specified in the cycle in `lists`. In this case, the acyclic prefix length of the result is the sum of the lengths of the lists specified in the acyclic prefix of `lists`, and the cycle length of the result is the sum of the lengths of the lists specified in the cycle of `lists`.

The following equivalences hold:

```          (append) == ()
(append h) == h
(append () h . t) == (append h . t)
(append (cons a b) h . t) == (cons a (append b h . t))
```
— Applicative: list-neighbors (list-neighbors list)

The `list-neighbors` applicative constructs and returns a list of all the consecutive sublists of `list` of length 2, in order. If `list` is nil, the result is nil. If `list` is non-nil, the length of the result is one less than the length of `list`. If `list` is cyclic, the result is structurally isomorphic to it (i.e., has the same acyclic prefix length and cycle length).

For example:

```          (list-neighbors (list 1 2 3 4)) ⇒ ((1 2) (2 3) (3 4))
```
— Applicative: filter (filter applicative list)

Applicative `filter` passes each of the elements of `list` as an argument to `applicative`, one at a time in no particular order, using a fresh empty environment for each call. The result of each call to `applicative` must be boolean, otherwise an error is signaled. `filter` constructs and returns a list of all elements of `list` on which `applicative` returned true, in the same order as in `list`. `applicative` is called exactly as many times as there are pairs in `list`. The resultant list has a cycle containing exactly those elements accepted by `applicative` that were in the cycle of `list`; if there were no such elements, the result is acyclic.

— Applicative: assoc (assoc object pairs [eq-pred?])

Applicative `assoc` returns the first element of `pairs` whose car is `eq-pred?` to `object`. If there is no such element in `pairs`, nil is returned. If `eq-pred?` is not supplied it defaults to `equal?`. SOURCE NOTE: the optional eq-pred? argument is from r7rs.

— Applicative: member? (member? object list [eq-pred?])

Applicative `member?` is a predicate that returns true iff some element of `list` is `eq-pred?` to `object`. If `eq-pred?` is not supplied, it defaults to `equal?`. SOURCE NOTE: the optional eq-pred? argument is from r7rs.

— Applicative: finite-list? (finite-list? . objects)

This is the type predicate for type finite-list. `finite-list?` returns true iff all the objects in `objects` are acyclic lists.

— Applicative: countable-list? (countable-list? . objects)

This is the type predicate for type list. `countable-list?` returns true iff all the objects in `objects` are lists.

— Applicative: reduce (reduce list binary identity [precycle incycle postcycle])

`binary` should be an applicative. If the short form is used, `list` should be an acyclic. If the long form is used, `precycle`, `incycle`, and `postcycle` should be applicatives.

If `list` is empty, applicative `reduce` returns `identity`. If `list` is nonempty but acyclic, applicative `reduce` uses binary operation `binary` to merge all the elements of `list` into a single object, using any associative grouping of the elements. That is, the sequence of objects initially found in `list` is repeatedly decremented in length by applying `binary` to a list of any two consecutive objects, replacing those two objects with the result at the point in the sequence where they occurred; and when the sequence contains only one object, that object is returned. If `list` is cyclic, the long form must be used. The elements of the cycle are passed, one at a time (but just once for each position in the cycle), as arguments to unary applicative `precycle`; the finite, cyclic sequence of results from `precycle` is reduced using binary applicative `incycle`; and the result from reducing the cycle is passed as an argument to unary applicative `postcycle`. Binary operation `binary` is used to reduce the sequence consisting of the elements of the acyclic prefix of `list` followed by the result returned by `postcycle`. The only constraint on the order of calls to the applicatives is that each call must be made before its result is needed (thus, parts of the reduction of the acyclic prefix may occur before the contribution from the cycle has been completed).

Each call to `binary`, `precycle`, `incycle`, or `postcycle` uses the dynamic environment of the call to `reduce`.

If `list` is acyclic with length `n >= 1`, `binary` is called `n - 1` times. If `list` is cyclic with acyclic prefix length `a` and cycle length `c`, `binary` is called `a` times; `precycle`, `c` times; `incycle`, `c - 1` times; and `postcycle`, once.

— Applicative: append! (append! . lists)

`lists` must be a nonempty list; its first element must be an acyclic nonempty list, and all of its elements except the last element (if any) must be acyclic lists.

The `append!` applicative sets the cdr of the last pair in each nonempty list argument to refer to the next non-nil argument, except that if there is a last non-nil argument, it isn’t mutated. It is an error for any two of the list arguments to have the same last pair. The result returned by this applicative is inert.

The following equivalences hold:

```          (append! v) == #inert
(append! u v . w) == (\$sequence (append! u v) (append! u . w))
```
— Applicative: copy-es (copy-es object)

Briefly, applicative `copy-es` returns an object initially `equal?` to `object` with a freshly constructed evaluation structure made up of mutable pairs. If `object` is not a pair, the applicative returns `object`. If `object` is a pair, the applicative returns a freshly constructed pair whose car and cdr would be suitable results for `(copy-es (car object))` and `(copy-es (cdr object))`, respectively. Further, the evaluation structure of the returned value is structurally isomorphic to that of `object` at the time of copying, with corresponding non-pair referents being `eq?`.

— Applicative: assq (assq object pairs)

Applicative `assq` returns the first element of `pairs` whose car is `eq?` to `object`. If there is no such element in `pairs`, nil is returned.

— Applicative: memq? (memq? object list)

Applicative `memq?` is a predicate that returns true iff some element of `list` is `eq?` to `object`.