[WARNING: This document is currently somewhat out-of-date with respect to recent discussions on the SRFI-1 mailing list. See http://srfi.schemers.org/srfi-1/mail-archive/maillist.html for the full archive. See ftp://ftp.ai.mit.edu/pub/shivers/srfi/small-stuff.txt ftp://ftp.ai.mit.edu/pub/shivers/srfi/issues.txt ftp://ftp.ai.mit.edu/pub/shivers/srfi/closed-issues.txt for a summary of the issues. -Olin 99/6/26 Too many damn procedure. Kill the eqv?, etc. specific stuff. Add the lists-as-sets stuff. ] The Scheme Underground list library Olin Shivers 98/10/16 Last Update: 99/7/13 This document can be viewed in emacs outline mode, with *'s introducing section headings -- just say M-x outline-mode in emacs. During the SRFI discussion period, the current draft may be found at ftp://ftp.ai.mit.edu/pub/shivers/srfi/list-doc.txt * Table of contents ------------------- Abstract Introduction Issues General rationale "Linear update" procedures Not included in this library The procedures Changes Source for the reference implementation * Abstract ---------- R5RS Scheme has an impoverished set of list-processing utilities, which is a problem for authors of portable code. This SRFI proposes a coherent and comprehensive set of list-processing procedures; it is accompanied by a reference implementation of the spec. The reference implementation is - portable - very efficient - completely open, public-domain source This draft SRFI includes an "Issues" section, whose contents should be resolved before this proposal is accepted as a completed SRFI. * Introduction -------------- I have for some time now been dissatisfied by the set of basic list and pair operations provided by R4RS/R5RS Scheme. Because this set is so small and basic, most implementations provide additional utilities, such as a list-filtering function, or a "left fold" operator, and so forth. But, of course, this introduces incompatibilities -- different Scheme implementations provide different sets of procedures. I have designed a full-featured library of procedures for list processing. While putting this library together, I checked as many Schemes as I could get my hands on. (I have a fair amount of experience with several of these already.) I missed Chez -- no on-line manual that I can find -- but I hit most of the other big, full-featured Schemes. The complete list of list-processing systems I checked is: R4RS/R5RS Scheme, MIT Scheme, Gambit, RScheme, MzScheme, slib, Common Lisp, Bigloo, guile, T, APL and the SML standard basis As a result, the library I am proposing is fairly rich. In parallel with designing this API, I have also written a reference implementation. I will place this implementation in the public domain after the discussion and review associated with the SRFI process has converged. The entire source of the reference implementation is appended to this document for the benefit of public review. A few notes about the reference implementation: - Although I got procedure names and specs from many Schemes, I wrote this code myself. Thus, there are *no* entanglements. Any Scheme implementor can pick this library up with no worries about copyright problems -- both commercial and non-commercial systems. - The code is written for portability and should be trivial to port to any Scheme. It has only two deviations from R4RS, clearly discussed in the comments: - One call to an ERROR procedure; - The PARTITION and PARTITION! procedures return multiple values, and thus make use of the R5RS CALL-WITH-VALUES and VALUES procedures. - It is written for clarity and well-commented. The current source is 912 lines of code, of which 277 are comments. - It is written for efficiency. Fast paths are provided for common cases. Side-effecting procedures such as FILTER! avoid unnecessary, redundant SET-CDR!s which would thrash a generational GC's write barrier and the store buffers of fast processors. Functions reuse longest common tails from input parameters to construct their results where possible. Constant-space iterations are used in preference to recursions; local recursions are used in preference to consing temporary intermediate data structures. This is not to say that the implementation can't be tuned up for a specific Scheme implementation. There are notes in comments addressing ways implementors can tune the reference implementation for performance. In short, I've written the reference implementation to make it as painless as possible for an implementor -- or a regular programmer -- to adopt this library and get good results with it. Here is a short list of the procedures provided by the list-lib package: xcons tree-copy make-list list-tabulate cons* list-copy proper-list? circular-list? dotted-list? not-pair? null-list? circular-list length+ iota first second third fourth fifth sixth seventh eighth ninth tenth take drop take-right drop-right take! drop-right! last last-pair zip unzip1 unzip2 unzip3 unzip4 unzip5 append! append-reverse append-reverse! unfold unfold/tail fold fold-right pair-fold pair-fold-right reduce reduce-right append-map append-map! map! pair-for-each filter-map map-in-order filter partition remove filter! partition! remove! find find-tail any every list-index del delq delv delete del! delq! delv! delete! mem ass alist-cons alist-copy delq-duplicates delv-duplicates delete-duplicates del-duplicates delq-duplicates! delv-duplicates! delete-duplicates! del-duplicates! alist-delete del-ass del-assq del-assv del-assoc alist-delete! del-ass! del-assq! del-assv! del-assoc! reverse! lset<= lset= lset-adjoin adjoin adjoinq adjoinv lset-union union unionq unionv lset-intersection intersection intersectionq intersectionv lset-difference list-difference list-differenceq list-differencev lset-xor list-xor list-xorq list-xorv lset-diff+intersection diff+intersection diff+intersectionq diff+intersectionv lset-adjoin! adjoin! adjoinq! adjoinv! lset-union! union! unionq! unionv! lset-intersection! intersection! intersectionq! intersectionv! lset-difference! list-difference! list-differenceq! list-differencev! lset-xor! list-xor! list-xorq! list-xorv! lset-diff+intersection! diff+intersection! diff+intersectionq! diff+intersectionv! Two R4RS/R5RS list-processing procedures are extended by this library: map for-each The following R4RS/R5RS list- and pair-processing procedures are also part of list-lib's exports, as defined by the R4RS report: cons pair? null? list length append reverse car cdr ... cdddar cddddr set-car! set-cdr! list-ref member memq memv assoc assq assv I follow the general Scheme convention (vector-length, string-ref) of placing the type-name before the action when naming procedures -- so we have LIST-COPY, TREE-COPY, PAIR-FOR-EACH rather than the perhaps more fluid, but less consistent, COPY-LIST, COPY-TREE, or FOR-EACH-PAIR. The two remaining R4RS/R5RS list-processing procedures are not included: list-tail (renamed DROP) list? (see PROPER-LIST?, CIRCULAR-LIST? and DOTTED-LIST?) * General rationale ------------------- A set of general criteria guided the design of this library. I don't require "destructive" (what I call "linear update") procedures to alter and recycle cons cells from the argument lists. They are allowed to, but not required to. (The reference implementations I have written *do* recycle the argument lists.) List-filtering procedures such as FILTER or DELETE do not disorder lists. Elements appear in the answer list in the same order as they appear in the argument list. This constrains implementation, but seems like a desirable feature, since in many uses of lists, order matters. (In particular, disordering an alist is definitely a bad idea.) Contrariwise, although my reference implementations of the list-filtering procedures share longest common tails between argument and answer lists, it not is part of the spec. Because lists are an inherently sequential data structure (unlike, say, vectors), list-inspection functions such as FIND, FIND-TAIL, FOR-EACH, ANY and EVERY commit to a left-to-right traversal order of their argument list. However, constructor functions, such as LIST-TABULATE and the mapping procedures (APPEND-MAP, APPEND-MAP!, MAP!, PAIR-FOR-EACH, FILTER-MAP) do *not* specify the dynamic order in which their procedural argument is applied to its various values. Predicates return useful true values wherever possible. Thus ANY must return the true value produced by its predicate, and EVERY returns the final true value produced by applying its predicate argument to the last element of its argument list. Functionality is provided both in pure and linear-update (potentially destructive) forms wherever this makes sense. No special status accorded Scheme's built-in equality functions. Any functionality provided in terms of EQ?, EQV?, EQUAL? is also available using a client-provided equality function. I left out sorting not because it isn't important, but because I figured it should go in its own library (and I will be submitting a sorting SRFI proposal in the near future). Proper design counts for more than backwards compatibility, but I have tried, ceteras paribus, to be as backwards-compatible as possible with existing list-processing libraries, in order to facilitate porting old code to run as a client of the procedures in this library. Name choices and semantics are, for the most part, in agreement with existing practice in many current Scheme systems. I have indicated some incompatibilities in the following text. These procedures are *not* "sequence generic" -- i.e., procedures that operate on either vectors and lists. They are list-specific. I prefer to keep the library simple and focussed. I have named these procedures without a qualifying initial "list-" lexeme, which is in keeping with the existing set of list-processing utilities in Scheme. * "Linear update" procedures ---------------------------- Many procedures in this library have "pure" and "linear update" variants. A "pure" procedure has no side-effects, and in particular does not alter its arguments in any way. A "linear update" procedure is allowed -- but *not* required -- to side-effect its arguments in order to construct its result. "Linear update" procedures are typically given names ending with an exclamation point. So, for example, (APPEND! list1 list2) is allowed to construct its result by simply using SET-CDR! to set the cdr of the last pair of list1 to point to list2, and then returning list1 (unless list1 is the empty list, in which case it would simply return list2). However, APPEND! may also elect to perform a pure append operation -- this is a legal definition of APPEND!: (define append! append) This is why we do not call these procedures "destructive" -- because they aren't *required* to be destructive. They are *potentially* destructive. What this means is that you may only apply linear-update procedures to values that you know are "dead" -- values that will never be used again in your program. This must be so, since you can't rely on the value passed to a linear-update procedure after that procedure has been called. It might be unchanged; it might be altered. The "linear" in "linear update" doesn't mean "linear time" or "linear space" or any sort of multiple-of-n kind of meaning. It's a fancy term that pointy-headed type theorists and pure functional programmers use to describe systems where you are only allowed to have exactly one reference to each variable. This provides a guarantee that the value bound to a variable is bound to no other variable. So when you *use* a variable in a variable reference, you "use it up." Knowing that no one else has a pointer to that value means the a system primitive is free to side-effect its arguments to produce what is, observationally, a pure-functional result. In the context of this library, "linear update" means you, the programmer, know there are *no other* live references to the value passed to the procedure -- after passing the value to one of these procedures, the value of the old pointer is indeterminate. Basically, you are licensing the Scheme implementation to alter the data structure if it feels like it -- you have declared you don't care either way. You get no help from Scheme in checking that the values you claim are "linear" really are. So you better get it right. Or play it safe and use the non-! procedures -- doesn't do any good to compute quickly if you get the wrong answer. Why go to all this trouble to define the notion of "linear update" and use it in a procedure spec, instead of the more common notion of a "destructive" operation? First, note that destructive list-processing procedures are almost always used in a linear-update fashion. This is in part required by the special case of operating upon the empty list, which can't be side-effected. This means that destructive operators are not pure side-effects -- they have to return a result. Second, note that code written using linear-update operators can be trivially ported to a pure, functional subset of Scheme by simply providing pure implementations of the linear-update operators. Finally, requiring destructive side-effects ruins opportunities to parallelise these operations -- and the places where one has taken the trouble to spell out destructive operations are usually exactly the code one would want a parallelising compiler to parallelise: the efficiency-critical kernels of the algorithm. Linear-update operations are easily parallelised. Going with a linear-update spec doesn't close off these valuable alternative implementation techniques. This list library is intended as a set of low-level, basic operators, so we don't want to exclude these possible implementations. The linear-update procedures in this library are take! drop-right! append! append-reverse! append-map! map! filter! partition! remove! del! delq! delv! delete! alist-delete! del-ass! del-assq! del-assv! del-assoc! delq-duplicates! delv-duplicates! delete-duplicates! del-duplicates! reverse! lset-adjoin! adjoin! adjoinq! adjoinv! lset-union! union! unionq! unionv! lset-intersection! intersection! intersectionq! intersectionv! lset-difference! list-difference! list-differenceq! list-differencev! lset-xor! list-xor! list-xorq! list-xorv! lset-diff+intersection! diff+intersection! diff+intersectionq! diff+intersectionv! * Improper lists ---------------- Scheme does not properly have a list type, just as C does not have a string type. Scheme has a binary-tuple type, from which one can build binary trees. There is an *interpretation* of Scheme values that allows one to treat these trees as lists. Further complications ensue from the fact that Scheme allows side-effects to these tuples, raising the possibility of lists of unbounded length, and trees of unbounded depth (that is, circular data structures). However, there is a simple view of the world of Scheme values that considers every value to be a list of some sort. That is, every value is either - a "proper list" -- a finite, ()-terminated list, such as (a b c) () (32); - a "dotted list" -- a finite, non-() terminated list, such as (a b c . d) (x . y) 42 george; - or a "circular list" -- an infinite, unterminated list. Note that the zero-length dotted lists are simply all the non-null, non-pair values. This view is captured by the predicates PROPER-LIST?, DOTTED-LIST?, and CIRCULAR-LIST?. List-lib users should note that dotted lists are not commonly used, and are considered by many Scheme programmers to be an ugly artifact of Scheme's lack of a true list type. (However, dotted lists do play a noticeable role in the *syntax* of Scheme, such as the "rest" parameters used by n-ary lambdas: (lambda (x y . rest) ...).) Dotted lists are *not* fully supported by list-lib. Most procedures are defined only on proper lists -- that is, finite, nil-terminated lists. The procedures that will also handle circular or dotted lists are specifically marked. While this design decision restricts the domain of possible arguments one can pass to these procedures, it has the benefit of allowing the procedures to catch the error cases where programmers inadvertently pass scalar values to a list procedure by accident, e.g. by switching the arguments to a procedure call. * The procedures ---------------- In a Scheme system that has a module or package system, these procedures should be contained in a module named "list-lib". The templates given below obey the following conventions for procedure formals: list A proper (finite, ()-terminated) list clist A proper or circular list flist A finite (proper or dotted) list pair A pair x, y, d, a Any value object, value Any value n, i A natural number (an integer >= 0) proc A procedure = A boolean procedure taking two arguments pred A boolean procedure taking one argument It is an error to pass a circular or dotted list to a procedure not defined to accept such an argument. Such a procedure may either signal an error or diverge when passed a circular list. ** Constructors =============== xcons d a -> pair (lambda (d a) (cons a d)) Of utility only as a value to be conveniently passed to higher-order procedures. (xcons '(b c) 'a) => (a b c) The name stands for "eXchanged CONS." tree-copy object -> object Recursively copies the list structure in OBJECT, stopping at non-pair leaves. (LIST-COPY does a "shallow" copy.) make-list n [fill] -> list Returns an N-element list, whose elements are all the value FILL. If the FILL argument is not given, the elements of the list may be arbitrary values. (make-list 4 'c) => (c c c c) (make-list 10) => (2 3 5 7 11 13 17 19 23 29) list-tabulate n init-proc -> list Returns an N-element list. Element i of the list, where 0 <= i < N, is produced by (INIT-PROC i). No guarantee is made about the dynamic order in which INIT-PROC is applied to these indices. (list-tabulate 4 values) => (0 1 2 3) cons* elt1 elt2 ... -> flist Like LIST, but the last argument provides the tail of the constructed list -- i.e., (cons* a1 a2 ... an) = (cons a1 (cons a2 (cons ... an))). This function is called LIST* in Common Lisp and about half of the Schemes that provide it; and CONS* in the other half. (cons* 1 2 3 4) => (1 2 3 . 4) (cons* 1) => 1 circular-list elt1 elt2 ... -> clist Constructs a circular list of the elements. (circular-list 'z 'q) => (z q z q z q ...) list-copy flist -> flist Copies the "spine" of the argument. (TREE-COPY does a deep copy.) zip list1 list2 ... -> list (lambda lists (apply map list lists)) If ZIP is passed N lists, it returns a list as long as the shortest of these lists, each element of which is an N-element list comprised of the corresponding elements from the parameter lists. (zip '(one two three) '(1 2 3) '(odd even odd even odd even odd even)) => ((one 1 odd) (two 2 even) (three 3 odd)) (zip '(1 2 3)) => ((1) (2) (3)) ** Predicates ============= Note: the predicates PROPER-LIST?, CIRCULAR-LIST?, and DOTTED-LIST? partition the entire universe of Scheme values. proper-list? x -> boolean Returns true iff X is a proper list -- a finite, nil-terminated list. More carefully: The empty list is a proper list. A pair whose cdr is a proper list is also a proper list: ::= () (Empty proper list) | (cons ) (Proper-list pair) Note that this definition rules out circular lists. This function is required to detect this case and return false. Nil-terminated lists are called "proper" lists by R5RS and Common Lisp. The opposite of proper is improper. R5RS binds this function to the variable LIST?. (not (proper-list? x)) = (or (dotted-list? x) (circular-list? x)) circular-list? x -> boolean True if X is a circular list. A circular list is a value such that for every n >= 0, cdr^n(x) is a pair. Terminology: The opposite of circular is finite. (not (circular-list? x)) = (or (proper-list? x) (dotted-list? x)) dotted-list? x -> boolean True if X is a finite, non-nil-terminated list. That is, there exists an n >= 0 such that cdr^n(x) is neither a pair nor (). This includes non-pair, non-() values (e.g. symbols, numbers), which are considered to be dotted lists of length 0. (not (dotted-list? x)) = (or (proper-list? x) (circular-list? x)) null-list? list -> boolean LIST is a proper or circular list. This procedure returns true if the argument is the empty list (), and false otherwise. It is an error to pass this procedure a value which is not a proper list. This procedure is recommended as the termination condition for list-processing procedures that are not defined on dotted lists. not-pair? x -> boolean (not (pair? x)) Provided as a procedure as it can be useful as the termination condition for list-processing procedures that wish to handle all finite lists, both proper and dotted. ** Selectors ============ first second third fourth fifth sixth seventh eighth ninth tenth: pair -> value Synonyms for car, cadr, caddr, ... (third '(a b c d e)) => c car+cdr pair -> [x y] (lambda (p) (values (car p) (cdr p))) This can, of course, be implemented more efficiently by a compiler. take x i -> value drop x i -> value TAKE returns the first I elements of list X. DROP returns all but the first I elements of list X. The returned list may share a common tail with the argument list. (take '(a b c d e) 2) => (a b) (drop '(a b c d e) 2) => (c d e) X may be any value -- a proper, circular, or dotted list: (take '(1 2 3 . d) 2) => (1 2) (drop '(1 2 3 . d) 2) => (3 . d) (drop '(1 2 3 . d) 3) => d For a legal I, TAKE and DROP partition the list in a manner which can be inverted with APPEND: (append (take x i) (drop x i)) = x take-right flist i -> value drop-right flist i -> value TAKE-RIGHT returns the last I elements of FLIST. DROP-RIGHT returns all but the last I elements of FLIST. The returned list may share a common tail with the argument list. (take-right '(a b c d e) 2) => (d e) (drop-right '(a b c d e) 2) => (a b c) X may be any finite list, either proper or dotted: (take-right '(1 2 3 . d) 2) => (2 3 . d) (drop-right '(1 2 3 . d) 2) => (1) (take-right '(1 2 3 . d) 0) => d For a legal I, TAKE-RIGHT and DROP-RIGHT partition the list in a manner which can be inverted with APPEND: (append (take x i) (drop x i)) = x take! x i -> list drop-right! flist i -> list TAKE! and DROP-RIGHT! are "linear-update" variants of TAKE and DROP-RIGHT: the procedure is allowed, but not required, to alter the argument list to produce the result. X is any list, either proper, circular or dotted. (take! '(1 3 5 7 9 . d) 2) => (1 3) If X is circular, TAKE! may return a shorter-than-expected list: (take! (circular-list 1 3 5) 8) => (1 3) (take! (circular-list 1 3 5) 8) => (1 3 5 1 3 5 1 3) FLIST may be any finite list, proper or dotted: (drop-right! '(1 3 5 7 9 . d) 2) => (1 3 5) last pair -> object last-pair pair -> pair LAST returns the last element of the non-empty, finite list PAIR. LAST-PAIR returns the last pair in the non-empty, finite list PAIR. (last '(a b c)) => c (last-pair '(a b c)) => (c) (last-pair '(a b c . d)) => (c . d) unzip1 list -> list unzip2 list -> [list list] unzip3 list -> [list list list] unzip4 list -> [list list list list] unzip5 list -> [list list list list list] UNZIP1 takes a list of lists, where every list must contain at least one element, and returns a list containing the initial element of each such list. That is, it returns (MAP CAR LISTS). UNZIP2 takes a list of lists, where every list must contain at least two elements, and returns two values: a list of the first elements, and a list of the second elements. UNZIP3 does the same for the first three elements of the lists, and so forth. (unzip2 '((1 one) (2 two) (3 three))) => (1 2 3) (one two three) length list -> integer length+ clist -> integer or #f Both LENGTH and LENGTH+ return the length of the argument. It is an error to pass a value to LENGTH which is not a proper list (finite and nil-terminated). In particular, this means an implementation may diverge or signal an error when LENGTH is applied to a circular list. LENGTH+, on the other hand, returns #F when applied to a circular list. The length of a proper list is a non-negative integer N such that CDR applied N times to the list produces the empty list. ** Append & reverse =================== append! list1 ... -> value A "linear-update" variant of APPEND -- this procedure is allowed, but not required, to alter cons cells in the argument lists to construct the result list. The *last* parameter is never altered; the result list may or may not share structure with this parameter. The last argument to APPEND may be any value at all. All other arguments must be proper lists. append-reverse rev-head tail -> value append-reverse! rev-head tail -> value APPEND-REVERSE returns (append (reverse rev-head) tail) It it provided because it is a common operation -- a common list-processing style calls for this exact operation to transfer values accumulated in reverse order onto the front of another list, and because the implementation is significantly more efficient than the simple composition it replaces. (But note that this pattern of iterative computation followed by a reverse can frequently be rewritten as a recursion, dispensing with the REVERSE and APPEND-REVERSE steps, and shifting temporary, intermediate storage from the heap to the stack, which is typically a win for reasons of cache locality and eager storage reclamation.) APPEND-REVERSE! is just the linear-update variant -- it is allowed, but not required, to alter REV-HEAD's cons cells to construct the result. reverse! list -> list Linear-update variant of reverse. Is permitted, but not required, to alter the argument's cons cells to produce the reversed list. ** Fold, unfold, and map ======================== unfold p f g seed -> list UNFOLD is best described by its basic recursion: (unfold p f g seed) = (if (p seed) '() (cons (f seed) (unfold p f g (g seed)))) P: Determines when to stop unfolding. F: Maps each seed value to the corresponding list element. G: Maps each seed value to next seed value. SEED: The "state" value for the unfold. UNFOLD is a fundamental list constructor, just as FOLD and FOLD-RIGHT are fundamental list consumers. While UNFOLD may seem a bit abstract to novice functional programmers, it can be used in a number of ways: (unfold (lambda (x) (= x 10)) ; The first 10 squares. (lambda (x) (* x x)) (lambda (x) (+ x 1)) 0) (unfold null? car cdr lis) ; Copy a proper list ;; Read current input port into a list of values: (unfold eof-object? values (lambda (x) (read)) (read)) This combinator sometimes is called an "anamorphism." unfold/tail p f g e seed -> list UNFOLD/TAIL allows you to specify the value to use when the recursion terminates. I.e. (unfold/tail p f g e seed) = (if (p seed) (e seed) (cons (f seed) (unfold p f g (g seed)))) ;;; Copy a possibly non-proper list: (unfold/tail not-pair? car cdr values lis) ;;; Append HEAD onto TAIL: (unfold/tail not-pair? car cdr (lambda (x) tail) head) This combinator sometimes is called an "apomorphism." fold kons knil clist1 clist2 ... -> value The fundamental list iterator. First, consider the single list-parameter case. If CLIST1 = (e1 e2 ... en), then this procedure returns (kons en ... (kons e2 (kons e1 knil)) ... ) That is, it obeys the (tail) recursion (fold kons knil lis) = (fold kons (kons (car lis) knil) (cdr lis)) (fold kons knil '()) = knil Examples: (fold + 0 lis) ; Add up the elements of LIS. (fold cons '() lis) ; Reverse LIS. (fold cons tail rev-head) ; See APPEND-REVERSE. ;; How many symbols in LIS? (fold (lambda (x count) (if (symbol? x) (+ count 1) count)) 0 lis) ;; Length of the longest string in LIS: (fold (lambda (s max-len) (max max-len (string-length s))) 0 lis) If N list arguments are provided, then the KONS function must take N+1 parameters: one element from each list, and the "seed" or fold state, which is initially KNIL. The fold operation terminates when the shortest list runs out of values: (fold cons* '() '(a b c) '(1 2 3 4 5)) => (c 3 b 2 a 1) At least one of the list arguments must be finite. fold-right kons knil clist1 clist2 ... -> value The fundamental list recursion operator. First, consider the single list-parameter case. If CLIST1 = (e1 e2 ... en), then this procedure returns (kons e1 (kons e2 ... (kons en knil))) That is, it obeys the recursion (fold-right kons knil lis) = (kons (car lis) (fold-right kons knil (cdr lis))) (fold-right kons knil '()) = knil Examples: (fold-right cons '() lis) ; Copy LIS. ;; Filter the even numbers out of LIS. (fold-right (lambda (x l) (if (even? x) (cons x l) l)) '() lis)) If N list arguments are provided, then the KONS function must take N+1 parameters: one element from each list, and the "seed" or fold state, which is initially KNIL. The fold operation terminates when the shortest list runs out of values: (fold-right cons* '() '(a b c) '(1 2 3 4 5)) => (a 1 b 2 c 3) At least one of the list arguments must be finite. pair-fold kons knil clist1 clist2 ... -> value Analogous to FOLD, but KONS is applied to successive sublists of the lists, rather than successive elements -- that is, KONS is applied to the pairs making up the lists, giving this (tail) recursion: (pair-fold kons knil lis) = (let ((tail (cdr lis))) (pair-fold kons (kons lis knil) tail)) The KONS function may reliably apply SET-CDR! to the pairs it is given without altering the sequence of execution. Example: ;;; Destructively reverse a list. (pair-fold (lambda (pair tail) (set-cdr! pair tail) pair) '() lis)) At least one of the list arguments must be finite. pair-fold-right kons knil clist1 clist2 ... -> value Holds the same relationship with FOLD-RIGHT that PAIR-FOLD holds with FOLD. Obeys the recursion (pair-fold-right kons knil lis) = (kons lis (pair-fold-right kons knil (cdr lis))) Example: (pair-fold-right cons '() '(a b c)) => ((a b c) (b c) (c)) At least one of the list arguments must be finite. reduce f ridentity list -> value REDUCE is a variant of FOLD. RIDENTITY should be a "right identity" of the procedure F -- that is, for any value X acceptable to F, (f x ridentity) = x REDUCE has the following definition: If LIST = (), return RIDENTITY. Otherwise, return (fold f (car x) (cdr x)). Note that RIDENTITY is used *only* in the empty-list case. You typically use REDUCE when applying F is expensive and you'd like to avoid the extra application incurred when FOLD applies F to the head of LIS and the identity -- for example, if F involves searching a file directory or performing a database query, this can be significant. In general, however, FOLD is useful in many contexts where REDUCE is not (consider the examples given in the FOLD definition -- only one of the five folds uses a function with a right identity. The other four may not be performed with REDUCE). Note: MIT Scheme and Haskell flips F's arg order for its REDUCE-LEFT and FOLD-LEFT. SML uses the same order chosen for this function. Common Lisp? reduce-right f ridentity list -> value REDUCE-RIGHT is the fold-right variant of REDUCE. map proc clist1 clist2 ... -> list for-each proc clist1 clist2 ... -> unspecified These two procedures are extended from their R5RS specification to allow the arguments to be of unequal length; they terminate when the shortest list runs out. At least one of the argument lists must be finite: (map + '(3 1 4 1) (circular-list 1 0)) => (4 1 5 1) append-map f clist1 clist2 ... -> value append-map! f clist1 clist2 ... -> value Equivalent to (apply append (map f clist1 clist2 ...)) and (apply append! (map f clist1 clist2 ...)) Map F over the elements of the lists, just as in the MAP function. However, the results of the applications are appended together to make the final result. APPEND-MAP uses APPEND to append the results together; APPEND-MAP! uses APPEND!. The dynamic order in which the various applications of F are made is not specified. Example: (append-map! (lambda (x) (list x (- x))) '(1 3 8)) => (1 -1 3 -3 8 -8) At least one of the list arguments must be finite. map! f list1 clist2 ... -> list Linear-update variant of MAP -- MAP! is allowed, but not required, to alter the cons cells of LIST1 to construct the result list. The dynamic order in which the various applications of F are made is not specified. In the n-ary case, CLIST2, CLIST3, ... must have at least as many elements as CLIST1. map-in-order f clist1 clist2 ... -> list A variant of the MAP procedure that guarantees to apply F across the elements of the LISTi arguments in a left-to-right order. This is useful for mapping procedures that both have side effects and return useful values. At least one of the list arguments must be finite. pair-for-each f clist1 clist2 ... -> unspecific Like FOR-EACH, but F is applied to successive sublists of the argument lists. That is, F is applied to the cons cells of the lists, rather than the lists' elements. These applications occur in left-to-right order. (pair-for-each (lambda (pair) (display pair) (newline)) '(a b c)) ==> (a b c) (b c) (c) At least one of the list arguments must be finite. filter-map f clist1 clist2 ... -> list Like MAP, but only true values are saved. (filter-map (lambda (x) (and (number? x) (* x x))) '(a 1 b 3 c 7)) => (1 9 49) The dynamic order in which the various applications of F are made is not specified. At least one of the list arguments must be finite. ** Filtering & partitioning =========================== filter pred list -> list Return all the elements of LIST that satisfy predicate PRED. The list is not disordered -- elements that appear in the result list occur in the same order as they occur in the argument list. The returned list may share a common tail with the argument list. The dynamic order in which the various applications of PRED are made is not specified. (filter even? '(0 7 8 8 43 -4)) => (0 8 8 -4) partition pred list -> [list list] Partitions the elements of LIST with predicate PRED, and returns two values -- the list of in-elements and the list of out-elements. The list is not disordered -- elements occur in the result lists in the same order as they occur in the argument list. The dynamic order in which the various applications of PRED are made is not specified. One of the returned lists may share a common tail with the argument list. (partition symbol? '(one 2 3 four five 6)) => (one four five) (2 3 6) remove pred list -> list Returns LIST without the elements that satisfy predicate PRED: (lambda (pred list) (filter (lambda (x) (not (pred x))) list)) The list is not disordered -- elements that appear in the result list occur in the same order as they occur in the argument list. The returned list may share a common tail with the argument list. The dynamic order in which the various applications of PRED are made is not specified. (remove even? '(0 7 8 8 43 -4)) => (7 43) filter! pred list -> list partition! pred list -> [list list] remove! pred list -> list Linear-update variants of FIND, PARTITION and REMOVE. These procedures are allowed, but not required, to alter the cons cells in the argument list to construct the result lists. ** Searching ============ The following procedures all search lists for a leftmost element satisfying some criteria. This means they do not always examine the entire list, thus there is no efficient way for them to reliably detect and signal an error when passed a dotted or circular list. Here are the general rules describing how these procedures work when applied to different kinds of lists: Proper lists: The standard, canonical behavior happens in this case. Dotted lists: It is an error to pass these procedures a dotted list that does not contain an element satisfying the search criteria. That is, it is an error if the procedure has to search all the way to the end of the dotted list. However, this SRFI does *not* specify anything at all about the behavior of these procedures when passed a dotted list containing an element satisfying the search criteria. It may finish successfully, signal an error, or perform some third action. Different implementations may provide different functionality in this case; code which is compliant to this SRFI may not rely on any particular behavior. Future SRFI's may refine SRFI-1 to define specific behavior in this case. In brief, SRFI-1 compliant code may not pass a dotted list argument to these procedures. Circular lists: It is an error to pass these procedures a circular list that does not contain an element satisfying the search criteria. Note that the procedure is not required to detect this case; it may simply diverge. It is, however, acceptable to search a circular list *if the search is successful* -- that is, if the list contains an element satisfying the search criteria. Here are some examples, using the FIND and ANY procedures as a canonical representatives: ;; Proper list -- success (find even? '(1 2 3)) => 2 (any even? '(1 2 3)) => #t ;; proper list -- failure (find even? '(1 7 3)) => #f (any even? '(1 7 3)) => #f ;; Failure is error on a dotted list. (find even? '(1 3 . x)) => error (any even? '(1 3 . x)) => error ;; The dotted list contains an element satisfying the search. ;; This case is not specified -- it could be success, an error, or some ;; third possibility. (find even? '(1 2 . x)) => error/undefined (any even? '(1 2 . x)) => error/undefined ; success, error or other. ;; circular list -- success (find even? (circular-list 1 6 3)) => 6 (any even? (circular-list 1 6 3)) => #t ;; circular list -- failure is error. Procedure may diverge. (find even? (circular-list 1 3)) => error (any even? (circular-list 1 3)) => error find pred clist -> value Return the first element of CLIST that satisfies predicate PRED; false if no element does. (find even? '(3 1 4 1 5 9)) => 4 Note that FIND has an ambiguity in its lookup semantics -- if FIND returns #F, you cannot tell (in general) if it found a #F element that satisfied PRED, or if it did not find any element at all. In many situations, this ambiguity cannot arise -- either the list being searched is known not to contain any #F elements, or the list is guaranteed to have an element satisfying PRED. However, in cases where this ambiguity can arise, you should use FIND-TAIL instead of FIND -- FIND-TAIL has no such ambiguity: (cond ((find-tail pred lis) => (lambda (pair) ...)) ; Handle (CAR PAIR) (else ...)) ; Search failed. find-tail pred clist -> pair or false Return the first pair of CLIST whose car satisfies PRED. If no pair does, return false. The dynamic order in which the various applications of PRED are made is not specified. FIND-TAIL can be viewed as a general-predicate variant of the MEMBER function. Examples: (find-tail even? '(3 1 37 -8 -5 0 0)) => (-8 -5 0 0) (find-tail even? '(3 1 37 -5)) => #f ;; MEMBER X LIS: (find-tail (lambda (elt) (equal? elt x)) lis) In the circular-list case, this procedure "rotates" the list. any pred clist1 clist2 ... -> value Applies the predicate across the lists, returning true if the predicate returns true on any application. If there are N list arguments CLIST1 ... CLISTn, then PRED must be a function taking N arguments and returning a boolean result. ANY applies PRED to the first elements of the CLISTi parameters. If this application returns a true value, ANY immediately returns that value. Otherwise, it iterates, applying PRED to the second elements of the CLISTi parameters, then the third, and so forth. The iteration stops when one of the lists runs out of values; in this case, ANY returns #F. This #F value is produced by a tail call to the final application of PRED. Note the difference between FIND and ANY -- FIND returns the element that satisfied the predicate; ANY returns the true value that the predicate produced. Like EVERY, ANY's name does not end with a question mark -- this is to indicate that it does not return a simple boolean (#T or #F), but a general value. (any integer? '(a 3 b 2.7)) => #T (any integer? '(a 3.1 b 2.7)) => #F (any < '(3 1 4 1 5) '(2 7 1 8 2)) => #T every pred clist1 clist2 ... -> value Applies the predicate across the lists, returning true if the predicate returns true on every application. If there are N list arguments CLIST1 ... CLISTn, then PRED must be a function taking N arguments and returning a boolean result. EVERY applies PRED to the first elements of the CLISTi parameters. If this application returns false, EVERY immediately returns false. Otherwise, it iterates, applying PRED to the second elements of the LISTi parameters, then the third, and so forth. The iteration stops when one of the lists runs out of values; in this case, EVERY returns the true value produced by its final application of PRED. This final application of PRED is a tail call. If one of the LISTi has no elements, EVERY returns #T. Like ANY, EVERY's name does not end with a question mark -- this is to indicate that it does not return a simple boolean (#T or #F), but a general value. At least one of the list arguments must be finite. list-index pred clist1 clist2 ... -> value Return the index of the leftmost element that satisfies PRED. If there are N list arguments CLIST1 ... CLISTn, then PRED must be a function taking N arguments and returning a boolean result. LIST-INDEX applies PRED to the first elements of the CLISTi parameters. If this application returns true, LIST-INDEX immediately returns zero. Otherwise, it iterates, applying PRED to the second elements of the CLISTi parameters, then the third, and so forth. When it finds a tuple of list elements that cause PRED to return true, it stops and returns the zero-based index of that position in the lists. The iteration stops when one of the lists runs out of values; in this case, LIST-INDEX returns #F. (list-index even? '(3 1 4 1 5 9)) => 2 (list-index < '(3 1 4 1 5 9 2 5 6) '(2 7 1 8 2)) => 1 (list-index = '(3 1 4 1 5 9 2 5 6) '(2 7 1 8 2)) => #f ** Deletion =========== del = x list -> list delq x list -> list delv x list -> list delete x list -> list DEL uses the comparison procedure = to find all elements of LIST that are equal to X, and deletes them from LIST. The dynamic order in which the various applications of = are made is not specified. DELQ uses EQ? to compare elements. DELV uses EQV? to compare elements. DELETE uses EQUAL? to compare elements. The list is not disordered -- elements that appear in the result list occur in the same order as they occur in the argument list. The result may share a common tail with the argument list. Note that fully general element deletion can be performed with the REMOVE and REMOVE! procedures, e.g.: ;; Delete all the even elements from LIS: (remove even? lis) The comparison procedure is used in this way: (= Ei X) That is, X is always the second argument, and a list element is always the first argument. The comparison procedure will be used to compare each element of LIST exactly once; the order in which it is applied to the various Ei is not specified. Thus, one can reliably remove all the numbers less than five from a list with (del < 5 list) del! = object list -> list delq! object list -> list delv! object list -> list delete! object list -> list Linear-update variants of DEL, DELQ, DELV and DELETE. These procedures are allowed, but not required, to alter the cons cells in their argument list to construct the result. del-duplicates = list -> list delq-duplicates list -> list delv-duplicates list -> list delete-duplicates list -> list These procedures remove duplicate elements from the list argument. If there are multiple equal elements in the argument list, the result list only contains the first or leftmost of these elements in the result. The order of these surviving elements is the same as in the original list -- these procedures do not disorder the list (hence it is useful for "cleaning up" association lists). The procedure used to compare elements varies among the different procedures. DELQ-DUPLICATES uses EQ?; DELV-DUPLICATES uses EQV?; DELETE-DUPLICATES uses EQUAL?; DEL-DUPLICATES uses the comparison procedure provided as its first parameter. If X comes before Y in LIST, then the comparison is performed (= X Y) The comparison procedure will be used to compare each pair of elements in LIST exactly once; the order in which it is applied to the various pairs is not specified. Implementations of these procedures are allowed to share common tails between argument and result lists -- for example, if the list argument contains only unique elements, these procedures may simply return exactly this list. Be aware that these procedures run in time O(n^2) for N-element lists. Uniquifying long lists can be accomplished in O(n lg n) time by sorting the list to bring equal elements together, then using a linear-time algorithm to remove equal elements. Alternatively, one can use algorithms based on element-marking, with linear-time results. (delq-duplicates '(a b a c a b c z)) => (a b c z) ;; Clean up an alist: (del-duplicates (lambda (x y) (eq? (car x) (car y))) '((a . 3) (b . 7) (a . 9) (c . 1))) => ((a . 3) (b . 7) (c . 1)) del-duplicates! = list -> list delq-duplicates! list -> list delv-duplicates! list -> list delete-duplicates! list -> list Linear-update variants of the above procedures. ** Searching & association lists ============================= mem = x list -> list ass = key alist -> entry These procedures are variants of MEMBER and ASSOC that allow the client to pass in the equality procedure = used to compare keys. The dynamic order in which the various applications of = are made is not specified. Note that fully general list and alist searching may be performed with the FIND-TAIL and FIND procedures, e.g. ;; Look up the first association in ALIST with an even key: (find (lambda (a) (even? (car a))) alist) The comparison procedure is used to compare the elements Ei of LIST to the key X in this way: (= Ei X) ; MEM -- list is (E1 ... En) (= (CAR Ei) KEY) ; ASS -- list is (E1 ... En) That is, the second argument is always X, and the first argument is one of the list elements. Thus one can reliably find the first entry of ALIST whose key is less than five with (ass < 5 ALIST) alist-cons key datum alist -> alist (lambda (k d a) (cons (cons k d) a)) Cons a new alist entry mapping KEY -> DATUM onto ALIST. alist-copy alist -> alist Make a fresh copy of ALIST. This means copying each pair that forms an association as well as the spine of the list, i.e. (lambda (a) (map (lambda (elt) (cons (car elt) (cdr elt))) a)) alist-delete = key alist -> alist del-ass = key alist -> alist del-assq key alist -> alist del-assv key alist -> alist del-assoc key alist -> alist ALIST-DELETE and DEL-ASS are synonyms. The procedure deletes all associations from ALIST with the given KEY, using key-comparison procedure =. The dynamic order in which the various applications of = are made is not specified. DEL-ASSQ uses EQ? to compare elements. DEL-ASSV uses EQV? to compare elements. DEL-ASSOC uses EQUAL? to compare elements. Return values may share common tails with the ALIST argument. The alist is not disordered -- elements that appear in the result alist occur in the same order as they occur in the argument alist. The comparison procedure is used to compare the element keys Ki of ALIST's entries to the key X in this way: (= Ki X) Thus, one can reliably remove all entries of ALIST whose key is less than five with (alist-delete < 5 list) alist-delete! = x alist -> alist del-ass! = x alist -> alist del-assq! x alist -> alist del-assv! x alist -> alist del-assoc! x alist -> alist These are linear-update variants. They are allowed, but not required, to alter cons cells from the ALIST parameter to construct the return value. * Set operations on lists ------------------------- lset<= = list1 list2 ... -> boolean Returns true iff every LISTi is a subset of LISTi+1, using = for the element equality procedure. The = procedure's first argument is from LISTi; its second is from LISTi+1. (lset<= eq? '(a) '(a b a) '(a b c c)) => #t lset= = list1 list2 ... -> boolean Returns true iff every LISTi is set-equal to LISTi+1, using = for the element equality procedure. "Set-equal" simply means that LISTi is a subset of LISTi+1, and LISTi+1 is a subset of LISTi. The = procedure's first argument is from LISTi; its second is from LISTi+1. (lset= eq? '(b e a) '(a e b) '(e e b a)) => #t lset-adjoin = list elt1 ... -> list Adds the ELTi elements not already in the list parameter to the result list. The result shares a common tail with the list parameter. The new elements are added to the front of the list, but no guarantees are made about their order. The = parameter is an equality procedure used to determine if an ELTi is already a member of LIST. Its first argument is from LIST; it's second is one of the ELTi. The list parameter is always a suffix of the result -- even if the list parameter contains repeated elements, these are not reduced. (lset-adjoin eq? '(a b c d c e) 'a 'e 'i 'o 'u) => (u o i a b c d c e) lset-union = list1 ... -> list Returns the union of the lists, using = for the element equality procedure. The = procedure's first argument is from LISTi; its second is from LISTi+1. LIST1 is a suffix or tail of the result. Elements that are repeated multiple times in a single list parameter may or may not occur multiple times in the result; however, an element that occurs once in more than one list parameter will only appear once in the result. Elements introduced by LIST2 or following parameters occur in no particular order. (lset-union eq? '(a b c d e) '(a e i o u)) => (u o i a b c d e) lset-intersection = list1 list2 ... -> list Returns the intersection of the lists, using = for the element equality procedure. The = procedure's first argument is from LISTi; its second is from LISTi+1. The result may share a common tail with any of the list parameters. Elements that are repeated multiple times in every list parameter may or may not occur multiple times in the result; however, an element that occurs only once in every list parameter will only appear once in the result. No constraint is placed on the ordering of the elements in the result. (lset-intersection eq? '(a b c d e) '(a e i o u)) => (a e) lset-difference = list1 list2 ... -> list Returns the difference of the lists, using = for the element equality procedure -- all the elements of LIST1 that do not appear in any of the other LISTi parameters. The = procedure's first argument is from LISTi; its second is from LISTi+1. The result may share a common tail with LIST1. Elements that are repeated multiple times in the LIST1 parameter will occur multiple times in the result. No constraint is placed on the ordering of the elements in the result. (lset-difference eq? '(a b c d e) '(a e i o u)) => (b c d) lset-xor = list1 ... -> list Returns the XOR of the lists, using = for the element equality procedure. If there are exactly two lists, this is all the elements that appear in exactly one of the two lists. The operation is associative, and thus extends to the n-ary case -- the elements that appear in an odd number of the lists. The result may share a common tail with any of the LISTi parameters. The = procedure's first argument is from LISTi; its second is from LISTi+1. A list element that occurs multiple times in a single list parameter may or may not appear multiple times in the result. For example, if LSET-XOR is applied to a single list parameter, it is permitted to return *exactly* that list for its result. No constraint is placed on the ordering of the elements in the result. (lset-xor eq? '(a b c d e) '(a e i o u)) => (d c b i o u) lset-diff+intersection = list1 list2 ... -> [list list] Returns two values -- the difference and the union of the lists. Is equivalent to (values (lset-difference = list1 list2 ...) (lset-intersection = list1 list2 ...)) but can be implemented more efficiently. The = procedure's first argument is from LIST1; its second is from one of the other LISTi. lset-union! = list1 ... -> list lset-intersection! = list1 list2 ... -> list lset-difference! = list1 list2 ... -> list lset-xor! = list1 ... -> list lset-diff+intersection! = list1 list2 ... -> [list list] These are linear-update variants. They are allowed, but not required, to use the cons cells in their first list parameter to construct their answer. LSET-UNION! is permitted to recycle cons cells from *any* of its list arguments. The following variants of the general lset procedures use EQUAL?, EQ?, and EQV? for element comparison, respectively. union list1 ... -> list union! list1 ... -> list unionq list1 ... -> list unionq! list1 ... -> list unionv list1 ... -> list unionv! list1 ... -> list intersection list1 list2 ... -> list intersection! list1 list2 ... -> list intersectionq list1 list2 ... -> list intersectionq! list1 list2 ... -> list intersectionv list1 list2 ... -> list intersectionv! list1 list2 ... -> list list-xor list1 ... -> list list-xor! list1 ... -> list list-xorq list1 ... -> list list-xorq! list1 ... -> list list-xorv list1 ... -> list list-xorv! list1 ... -> list adjoin list elt1 ... -> list adjoinq list elt1 ... -> list adjoinv list elt1 ... -> list list-difference list1 list2 ... -> list list-differenceq list1 list2 ... -> list list-differencev list1 list2 ... -> list list-difference! list1 list2 ... -> list list-differenceq! list1 list2 ... -> list list-differencev! list1 list2 ... -> list diff+intersection list1 list2 ... -> list diff+intersectionq list1 list2 ... -> list diff+intersectionv list1 list2 ... -> list diff+intersection! list1 list2 ... -> list diff+intersectionq! list1 list2 ... -> list diff+intersectionv! list1 list2 ... -> list * Changes --------- ** From 98/10/16 netnews-posted version These changes are due to comments I received from the initial posting: - Changed name of NTH back to R5RS name, LIST-REF. The index returned is not ordinal (1-based) as the name "NTH" would lead you to believe, but cardinal (0-based), as is consistent with the other VECTOR-INDEX, STRING-INDEX procedures. Brian Harvey pointed out this problem. - Added CIRCULAR-LIST, :IOTA, IOTA:, LIST-INDEX, ZIP, UNZIP, MAP-IN-ORDER :IOTA and IOTA: generalise the many requests for an iota function. MAP-IN-ORDER as requested by Maciej Stachowiak. I think CIRCULAR-LIST is revolting, but it is in by popular demand. - Removed terminal ? from ANY? and EVERY? As requested by Kelsey. - Made ANY, EVERY, FOLDL, FOLDR, PAIR-FOLDL, PAIR-FOLDR n-ary. Many requests for this, some from Rice. - Added right-duplicate deletion procedures (DELQ-DUPLICATES, et al.) (As requested by Phil Bewig.) Current total: 89 procedures (plus R5RS imports) ** 98/11/15 - Added some run-time safety checks to reference implementation at urging of Felleisen. - Added CAR+CDR - Added text requiring procs to handle improper lists gracefully, and examples. - Added text specifying the name of the package, if there is one, that contains these bindings. ** 98/12/26 - Added PROPER-LIST?. Changed MAKE-LIST to default the list elements to unspecified values, as requested by Egorov. Renamed LIST* to CONS*, a widely requested change. Changed .IOTA and IOTA. to :IOTA and IOTA:, as the former identifiers are not a legal R5RS (argh). ** 99/4/18 - Added LENGTH+, which handles circular lists. - Added DOTTED-LIST? and CIRCULAR-LIST? * Source for the reference implementation ----------------------------------------- The current source can be found at ftp://ftp.ai.mit.edu/pub/shivers/srfi/list-lib.scm It will appear here in the final SRFI. * Ispell "buffer local" dictionary ---------------------------------- Ispell dumps "buffer local" words here. Please ignore. LocalWords: RS SRFI Chez RScheme MzScheme slib Bigloo APL SML API CDR GC's LocalWords: EQ consing lib xcons unzip del delq delv mem LocalWords: alist assq assv assoc cdr cdddar cddddr ref memq memv LocalWords: proc lis accessor ary TAIL's NCONS EQV rcons Contrariwise LocalWords: paribus lexeme parallelise Destructuring init FP LocalWords: generalisation elt cadr caddr rev kons knil len rzero LZERO LocalWords: arg LISTi pred cond LISTn ANY's EVERY's Uniquifying lg LocalWords: eq netnews generalise Maciej Stachowiak al Bewig LocalWords