Pairs and lists

— 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: cadr (cadr pair)
— Applicative: cdar (cdar pair)
— Applicative: cddr (cddr pair)
— Applicative: caaar (caaar pair)
— Applicative: caadr (caadr pair)
— Applicative: cadar (cadar pair)
— Applicative: caddr (caddr pair)
— Applicative: cdaar (cdaar pair)
— Applicative: cdadr (cdadr pair)
— Applicative: cddar (cddar pair)
— Applicative: cdddr (cdddr pair)
— Applicative: caaaar (caaaar pair)
— Applicative: caaadr (caaadr pair)
— Applicative: caadar (caadar pair)
— Applicative: caaddr (caaddr pair)
— Applicative: cadaar (cadaar pair)
— Applicative: cadadr (cadadr pair)
— Applicative: caddar (caddar pair)
— Applicative: cadddr (cadddr pair)
— Applicative: cdaaar (cdaaar pair)
— Applicative: cdaadr (cdaadr pair)
— Applicative: cdadar (cdadar pair)
— Applicative: cdaddr (cdaddr pair)
— Applicative: cddaar (cddaar pair)
— Applicative: cddadr (cddadr 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 li