[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 ] The Scheme Underground list library Olin Shivers 98/10/16 Last Update: 98/11/9 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 circular-list proper-list? circular-list? dotted-list? not-pair? :iota iota: first second third fourth fifth sixth seventh eighth ninth tenth take drop take! drop! last last-pair zip unzip2 unzip3 unzip4 unzip5 append! append-reverse append-reverse! unfold unfold/tail foldl foldr pair-foldl pair-foldr reducel reducer 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! length+ 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 map for-each 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 procedure is not included: list-tail (see 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, MAP-IN-ORDER), 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 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. Procedures that operate upon lists shall handle "improper" or non-null-terminated lists gracefully. * "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! 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! * Not included in this library ------------------------------ The following items are not in this library: Sort routines Procedures supporting lists-as-sets operations Destructuring/pattern-matching macro They deserve their own SRFI specs. I have three written proposals for the first two of these items (sorting, and two lists-as-sets packages) that I will be submitting shortly as SRFI proposals. One might argue that the lists-as-sets procedures should be part of this library. * The procedures ---------------- In a Scheme system that has a module or package system, these procedures should be contained in a module named "list-lib". ** 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." A possible alternative name is "rcons." But this is not a super-important issue. 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) 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) :iota to -> list :iota from to -> list :iota from to step -> list iota: to -> list iota: from to -> list iota: from to step -> list Produce simple numeric sequences over a half-open interval. FROM, TO, and STEP are numbers (that is, not necessarily integers). FROM defaults to 0; STEP defaults to 1. In the simple one-argument, integer case, (:IOTA N) returns the N-element list (0 1 2 ... n-1); (IOTA: N) returns the N-element list (1 2 ... n). :IOTA gives the half-open interval that includes its left bound. IOTA: gives the half-open interval that includes its right bound. The mnemonic is that the colon indicates inclusion of the bound. In general, these procedures return the list whose elements are of the form FROM + i * STEP where 0 <= i < ceiling((TO-FROM)/STEP) (:IOTA) 0 < i <= floor((TO-FROM)/STEP) (IOTA:) It is an error to request a list with a negative number of elements -- i.e., the rightmost element of the above two inequalities should be non-negative. These procedures are a generalisation of the APL primitive of the same name. (:iota 9) => 0 1 2 3 4 5 6 7 8 (:iota 3 9) => 3 4 5 6 7 8 (:iota 3 9 2) => 3 5 7 (:iota 3 10 2) => 3 5 7 9 (iota: 9) => 1 2 3 4 5 6 7 8 9 (iota: 3 9) => 4 5 6 7 8 9 (iota: 3 9 2) => 5 7 9 (iota: 3 10 2) => 5 7 9 (:iota 10 3 -2) => (10 8 6 4) (iota: 10 3 -2) => (8 6 4) (:iota 10 10 -2) => () (:iota 10 5) => ; Requests -5 elements! (:iota 0 1 1/10) => (0 1/10 1/5 3/10 2/5 1/2 3/5 7/10 4/5 9/10) cons* elt1 elt2 ... -> object 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 ... -> list Constructs a circular list of the elements. (circular-list 'z 'q) => (z q z q z q ...) list-copy list -> list Copies the spine of the argument. (TREE-COPY does a deep copy.) (lambda (lis) (map values lis)) 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 ============= not-pair? x -> boolean (not (pair? x)) Provided as a procedure as it is useful as the termination condition for list-processing functions. 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?, which is somewhat confusing. (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)) ** Selectors ============ first second third fourth fifth sixth seventh eighth ninth tenth: pair -> object 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 list i -> list take! list i -> list drop list i -> list drop! list i -> list If I >= 0, TAKE returns the first I elements of LIST. If I <= 0, TAKE returns the last -I elements of LIST. If I >= 0, DROP returns all but the first I elements of LIST. If I <= 0, DROP returns all but the last -I elements of LIST. The returned list may share a common tail with the argument list. TAKE! and DROP! are "linear-update" variants: the procedure is allowed, but not required, to alter the argument list to produce the result. (take '(a b c d e) 2) => (a b) (take '(a b c d e) -2) => (d e) (drop '(a b c d e) 2) => (c d e) (drop '(a b c d e) -2) => (a b c) last pair -> value last-pair pair -> pair LAST returns the last element of the non-empty list PAIR. LAST-PAIR returns the last pair in the non-empty 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+ list -> integer or #f Both LENGTH and LENGTH+ return the length of the argument. If the argument is a circular list, LENGTH either diverges or reports an error; LENGTH+ returns #F. The length of a list is a non-negative integer N such that CDR applied N times to the list produces a non-pair. Thus the length of any non-pair, such as an integer, symbol, or string, is zero. ** Append & reverse =================== append! list1 ... -> list 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. Improper lists: (append! (cons* 1 2 'x) '(a b c)) => (1 2 a b c) append-reverse rev-head tail -> list append-reverse! rev-head tail -> list 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. Improper lists: (append-reverse '(a b . c) '(d e . f)) -> (b a d e . f) 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 FOLDL and FOLDR 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." foldl kons knil list1 list2 ... -> value The fundamental list iterator. First, consider the single list-parameter case. If LIST1 = (e1 e2 ... en), then this procedure returns (kons en ... (kons e2 (kons e1 knil)) ... ) That is, it obeys the (tail) recursion (foldl kons knil lis) = (foldl kons (kons (car lis) knil) (cdr lis)) (foldl kons knil '()) = knil Examples: (foldl + 0 lis) ; Add up the elements of LIS. (foldl cons '() lis) ; Reverse LIS. (foldl cons tail rev-head) ; See APPEND-REVERSE. ;; How many symbols in LIS? (foldl (lambda (x count) (if (symbol? x) (+ count 1) count)) 0 lis) ;; Length of the longest string in LIS: (foldl (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: (foldl cons* '() '(a b c) '(1 2 3 4 5)) => (c 3 b 2 a 1) Improper lists: (foldl + 0 '(1 2 3 . x)) => 6 foldr kons knil list1 list2 ... -> value The fundamental list recursion operator. First, consider the single list-parameter case. If LIST1 = (e1 e2 ... en), then this procedure returns (kons e1 (kons e2 ... (kons en knil))) That is, it obeys the recursion (foldr kons knil lis) = (kons (car lis) (foldr kons knil (cdr lis))) (foldr kons knil '()) = knil Examples: (foldr cons '() lis) ; Copy LIS. ;; Filter the even numbers out of LIS. (foldr (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: (foldr cons* '() '(a b c) '(1 2 3 4 5)) => (a 1 b 2 c 3) Improper lists: (foldr cons '() '(a b . c)) => (a b) pair-foldl kons knil list1 list2 ... -> value Analogous to FOLDL, 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-foldl kons knil lis) = (let ((tail (cdr lis))) (pair-foldl 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-foldl (lambda (pair tail) (set-cdr! pair tail) pair) '() lis)) Improper lists: (pair-foldl cons '() '(a b . c)) => ((b . c) (a b . c)) pair-foldr kons knil list1 list2 ... -> value Holds the same relationship with FOLDR that PAIR-FOLDL holds with FOLDL. Obeys the recursion (pair-foldr kons knil lis) = (kons lis (pair-foldr kons knil (cdr lis))) Example: (pair-foldr cons '() '(a b c)) => ((a b c) (b c) (c)) Improper lists: (pair-foldr cons '() '(a b . c)) => ((a b . c) (b . c)) reducel f ridentity list -> value REDUCEL is a variant of FOLDL. RIDENTITY should be a "right identity" of the procedure F -- that is, for any value X acceptable to F, (f x ridentity) = x REDUCEL has the following definition: If LIST = (), return RIDENTITY. If LIST = (x), return X. Otherwise, return (foldl f (car x) (cdr x)). Note that RIDENTITY is used *only* in the empty-list case. You typically use REDUCEL when applying F is expensive and you'd like to avoid the extra application incurred when FOLDL 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, FOLDL is useful in many contexts where REDUCEL is not (consider the examples given in the FOLDL definition -- only one of the five folds uses a function with a right identity. The other four may not be performed with REDUCEL). 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? reducer f ridentity list -> value REDUCER is the fold-right variant of REDUCEL. append-map f list1 list2 ... -> list append-map! f list1 list2 ... -> list 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) Improper lists: (append-map values '((a b) (c d) (e f) . foo)) => (a b c d) map! f list1 list2 ... -> 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, LIST2, LIST3, ... must have at least as many elements as LIST1. Improper lists: (map! (lambda (n) (+ n 1)) (cons* 3 1 4 'x)) => (4 2 5 . x) map-in-order f list1 list2 ... -> 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. pair-for-each f list1 list2 ... -> 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) filter-map f list1 list2 ... -> 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. ** 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 ============ find pred list -> value Return the first element of LIST that satisfies predicate PRED; false if no element does. The dynamic order in which the various applications of PRED are made is not specified. (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 list -> pair or false Return the first pair of list 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) any pred list1 list2 ... -> value Applies the predicate across the lists, returning true if the predicate returns true on any application. If there are N list arguments LIST1 ... LISTn, then PRED must be a function taking N arguments and returning a boolean result. ANY applies PRED to the first elements of the LISTi parameters. If this application returns a true value, ANY immediately returns that value. 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, ANY returns #F. ANY's application of PRED the the last element of LIST is a tail call. 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 list1 list2 ... -> value Applies the predicate across the lists, returning true if the predicate returns true on every application. If there are N list arguments LIST1 ... LISTn, then PRED must be a function taking N arguments and returning a boolean result. EVERY applies PRED to the first elements of the LISTi 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. The application of EVERY to the last elements of the LISTi lists 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. list-index pred list1 list2 ... -> value Return the index of the leftmost element that satisfies PRED. Applies the predicate across the lists, returning the index of the list position that satisfies PRED. If there are N list arguments LIST1 ... LISTn, then PRED must be a function taking N arguments and returning a boolean result. LIST-INDEX applies PRED to the first elements of the LISTi parameters. If this application returns true, LIST-INDEX immediately returns zero. Otherwise, it iterates, applying PRED to the second elements of the LISTi 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 function = 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) 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. 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) 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. 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. * 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 foldl foldr del reducel 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