source: project/wiki/eggref/5/srfi-1 @ 36485

Last change on this file since 36485 was 36485, checked in by mario, 11 months ago

eggref/5/srfi-1: release note for version 0.4

File size: 53.1 KB
Line 
1[[tags: egg]]
2
3== srfi-1
4
5[[toc:]]
6
7
8=== Introduction
9
10SRFI 1 (list library) procedures.  A few procedures that can be found in R5RS, such as {{car}} and {{append}}, are omitted below.  For more information, see the
11[[http://srfi.schemers.org/srfi-1/srfi-1.html|original SRFI 1 document]].
12
13=== The procedures
14
15The templates given below obey the following conventions for procedure
16formals:
17
18<table>
19<tr><th>LIST</th><td>A proper (finite, nil-terminated) list</td></tr>
20<tr><th>CLIST</th><td>A proper or circular list</td></tr>
21<tr><th>FLIST</th><td>A finite (proper or dotted) list</td></tr>
22<tr><th>PAIR</th><td>A pair</td></tr>
23<tr><th>X, Y, D, A</th><td>Any value</td></tr>
24<tr><th>OBJECT, VALUE</th><td>Any value</td></tr>
25<tr><th>N, I</th><td>A natural number (an integer >= 0)</td></tr>
26<tr><th>PROC</th><td>A procedure</td></tr>
27<tr><th>PRED</th><td>A procedure whose return value is treated as a boolean</td></tr>
28<tr><th>=</th><td>A boolean procedure taking two arguments</td></tr></table>
29
30It is an error to pass a circular or dotted list to a procedure not defined
31to accept such an argument.
32
33
34==== Constructors
35
36<procedure>(xcons d a) -> pair</procedure><br>
37
38
39 (lambda (d a) (cons a d))
40
41Of utility only as a value to be conveniently passed to higher-order
42procedures.
43
44
45 (xcons '(b c) 'a) => (a b c)
46
47
48The name stands for "eXchanged CONS."
49
50<procedure>(cons* elt_1 elt_2 ...) -> object</procedure><br>
51
52Like {{list}}, but the last argument provides the tail of the constructed
53list, returning
54
55{{ (cons ELT_1 (cons ELT_2 (cons ... ELT_N))) }}
56
57This function is called {{list*}} in Common Lisp and about half of the
58Schemes that provide it, and {{cons*}} in the other half.
59
60
61 (cons* 1 2 3 4) => (1 2 3 . 4)
62 (cons* 1) => 1
63
64<procedure>(make-list n [fill]) -> list</procedure><br>
65
66Returns an N-element list, whose elements are all the value FILL. If the
67FILL argument is not given, the elements of the list may be arbitrary
68values.
69
70
71 (make-list 4 'c) => (c c c c)
72
73<procedure>(list-tabulate n init-proc) -> list</procedure><br>
74
75Returns an N-element list. Element I of the list, where 0 <= I < N, is
76produced by {{(INIT-PROC I)}}. No guarantee is made about the dynamic order
77in which INIT-PROC is applied to these indices.
78
79
80 (list-tabulate 4 values) => (0 1 2 3)
81
82<procedure>(list-copy flist) -> flist</procedure><br>
83
84Copies the spine of the argument.
85
86<procedure>(circular-list elt_1 elt_2 ...) -> list</procedure><br>
87
88Constructs a circular list of the elements.
89
90
91 (circular-list 'z 'q) => (z q z q z q ...)
92
93
94<procedure>(iota count [start step]) -> list</procedure><br>
95
96Returns a list containing the elements
97
98
99 (START START+STEP ... START+(COUNT-1)*STEP)
100
101
102The START and STEP parameters default to 0 and 1, respectively. This
103procedure takes its name from the APL primitive.
104
105
106 (iota 5) => (0 1 2 3 4)
107 (iota 5 0 -0.1) => (0 -0.1 -0.2 -0.3 -0.4)
108
109
110==== Predicates
111
112Note: the predicates {{proper-list?}}, {{circular-list?}}, and
113{{dotted-list?}} partition the entire universe of Scheme values.
114
115<procedure>(proper-list? x) -> boolean</procedure><br>
116
117Returns true iff X is a proper list -- a finite, nil-terminated list.
118
119More carefully: The empty list is a proper list. A pair whose cdr is a
120proper list is also a proper list:
121
122
123 <proper-list> ::= ()                            (Empty proper list)
124               |   (cons <x> <proper-list>)      (Proper-list pair)
125
126
127Note that this definition rules out circular lists. This function is
128required to detect this case and return false.
129
130Nil-terminated lists are called "proper" lists by R5RS and Common Lisp. The
131opposite of proper is improper.
132
133R5RS binds this function to the variable {{list?}}.
134
135
136 (not (proper-list? X)) = (or (dotted-list? X) (circular-list? X))
137
138<procedure>(circular-list? x) -> boolean</procedure><br>
139
140True if X is a circular list. A circular list is a value such that for
141every N >= 0, cdr^N(X) is a pair.
142
143Terminology: The opposite of circular is finite.
144
145
146 (not (circular-list? X)) = (or (proper-list? X) (dotted-list? X))
147
148
149<procedure>(dotted-list? x) -> boolean</procedure><br>
150
151True if X is a finite, non-nil-terminated list. That is, there exists an N >=
1520 such that cdr^N(X) is neither a pair nor (). This includes non-pair,
153non-() values (''e.g.'' symbols, numbers), which are considered to be
154dotted lists of length 0.
155
156
157 (not (dotted-list? X)) = (or (proper-list? X) (circular-list? X))
158
159<procedure>(null-list? list) -> boolean</procedure><br>
160
161LIST is a proper or circular list. This procedure returns true if the
162argument is the empty list (), and false otherwise. It is an error to
163pass this procedure a value which is not a proper or circular list. This
164procedure is recommended as the termination condition for list-processing
165procedures that are not defined on dotted lists.
166
167<procedure>(not-pair? x) -> boolean</procedure><br>
168
169
170 (lambda (x) (not (pair? x)))
171
172Provided as a procedure as it can be useful as the termination condition
173for list-processing procedures that wish to handle all finite lists, both
174proper and dotted.
175
176<procedure>(list= elt= list_1 ...) -> boolean</procedure><br>
177
178Determines list equality, given an element-equality procedure. Proper
179list A equals proper list B if they are of the same length, and
180their corresponding elements are equal, as determined by ELT=. If the
181element-comparison procedure's first argument is from LIST_I, then its
182second argument is from LIST_I+1, ''i.e.'' it is always called as {{(ELT= A
183B)}} for A an element of list A, and B an element of list B.
184
185In the N-ary case, every LIST_I is compared to LIST_I+1 (as opposed, for
186example, to comparing LIST_1 to every LIST_I, for I>1). If there are no
187list arguments at all, {{list=}} simply returns true.
188
189It is an error to apply {{list=}} to anything except proper lists. While
190implementations may choose to extend it to circular lists, note that it
191cannot reasonably be extended to dotted lists, as it provides no way to
192specify an equality procedure for comparing the list terminators.
193
194Note that the dynamic order in which the ELT= procedure is applied to pairs
195of elements is not specified. For example, if {{list=}} is applied to three
196lists, A, B, and C, it may first completely compare A to B, then compare
197B to C, or it may compare the first elements of A and B, then the first
198elements of B and C, then the second elements of A and B, and so forth.
199
200The equality procedure must be consistent with {{eq?}}. That is, it must be
201the case that
202
203{{(eq? X Y)}} => {{(ELT= X Y)}}.
204
205Note that this implies that two lists which are {{eq?}} are always
206LIST=, as well; implementations may exploit this fact to "short-cut" the
207element-by-element comparisons.
208
209
210 (list= eq?) => #t       ; Trivial cases
211 (list= eq? '(a)) => #t
212
213
214==== Selectors
215
216<procedure>(first pair) -> object</procedure><br>
217<procedure>(second pair) -> object</procedure><br>
218<procedure>(third pair) -> object</procedure><br>
219<procedure>(fourth pair) -> object</procedure><br>
220<procedure>(fifth pair) -> object</procedure><br>
221<procedure>(sixth pair) -> object</procedure><br>
222<procedure>(seventh pair) -> object</procedure><br>
223<procedure>(eighth pair) -> object</procedure><br>
224<procedure>(ninth pair) -> object</procedure><br>
225<procedure>(tenth pair) -> object</procedure><br>
226
227Synonyms for {{car}}, {{cadr}}, {{caddr}}, ...
228
229
230 (third '(a b c d e)) => c
231
232<procedure>(car+cdr pair) -> [x y]</procedure><br>
233
234The fundamental pair deconstructor:
235
236
237 (lambda (p) (values (car p) (cdr p)))
238
239This can, of course, be implemented more efficiently by a compiler.
240
241<procedure>(take x i) -> list</procedure><br>
242<procedure>(drop x i) -> object</procedure><br>
243
244{{take}} returns the first I elements of list X. {{drop}} returns all but
245the first I elements of list X.
246
247
248 (take '(a b c d e)  2) => (a b)
249 (drop '(a b c d e)  2) => (c d e)
250
251X may be any value -- a proper, circular, or dotted list:
252
253
254 (take '(1 2 3 . d) 2) => (1 2)
255 (drop '(1 2 3 . d) 2) => (3 . d)
256 (take '(1 2 3 . d) 3) => (1 2 3)
257 (drop '(1 2 3 . d) 3) => d
258
259
260For a legal I, {{take}} and {{drop}} partition the list in a manner which
261can be inverted with {{append}}:
262
263
264 (append (take X I) (drop X I)) = X
265
266
267{{drop}} is exactly equivalent to performing I cdr operations on X; the
268returned value shares a common tail with X. If the argument is a list
269of non-zero length, {{take}} is guaranteed to return a freshly-allocated
270list, even in the case where the entire list is taken, ''e.g.'' {{(take lis
271(length lis))}}.
272
273<procedure>(take-right flist i) -> object</procedure><br>
274<procedure>(drop-right flist i) -> list</procedure><br>
275
276{{take-right}} returns the last I elements of FLIST. {{drop-right}} returns
277all but the last I elements of FLIST.
278
279
280 (take-right '(a b c d e) 2) => (d e)
281 (drop-right '(a b c d e) 2) => (a b c)
282
283The returned list may share a common tail with the argument list.
284
285FLIST may be any finite list, either proper or dotted:
286
287
288 (take-right '(1 2 3 . d) 2) => (2 3 . d)
289 (drop-right '(1 2 3 . d) 2) => (1)
290 (take-right '(1 2 3 . d) 0) => d
291 (drop-right '(1 2 3 . d) 0) => (1 2 3)
292
293
294For a legal I, {{take-right}} and {{drop-right}} partition the list in a
295manner which can be inverted with {{append}}:
296
297
298 (append (take FLIST I) (drop FLIST I)) = FLIST
299
300
301{{take-right}}'s return value is guaranteed to share a common tail with
302FLIST. If the argument is a list of non-zero length, {{drop-right}} is
303guaranteed to return a freshly-allocated list, even in the case where
304nothing is dropped, ''e.g.'' {{(drop-right lis 0)}}.
305
306<procedure>(take! x i) -> list</procedure><br>
307<procedure>(drop-right! flist i) -> list</procedure><br>
308
309{{take!}} and {{drop-right!}} are "linear-update" variants of {{take}} and
310{{drop-right}}: the procedure is allowed, but not required, to alter the
311argument list to produce the result.
312
313If X is circular, {{take!}} may return a shorter-than-expected list:
314
315
316 (take! (circular-list 1 3 5) 8) => (1 3)
317 (take! (circular-list 1 3 5) 8) => (1 3 5 1 3 5 1 3)
318
319<procedure>(split-at x i) -> [list object]</procedure><br>
320<procedure>(split-at! x i) -> [list object]</procedure><br>
321
322{{split-at}} splits the list X at index I, returning a list of the first I
323elements, and the remaining tail. It is equivalent to
324
325
326 (values (take x i) (drop x i))
327
328{{split-at!}} is the linear-update variant. It is allowed, but not
329required, to alter the argument list to produce the result.
330
331
332 (split-at '(a b c d e f g h) 3) =>
333     (a b c)
334     (d e f g h)
335
336<procedure>(last pair) -> object</procedure><br>
337<procedure>(last-pair pair) -> pair</procedure><br>
338
339{{last}} returns the last element of the non-empty, finite list PAIR.
340{{last-pair}} returns the last pair in the non-empty, finite list PAIR.
341
342
343 (last '(a b c)) => c
344 (last-pair '(a b c)) => (c)
345
346
347==== Miscellaneous
348
349<procedure>(length+ clist) -> integer or #f</procedure><br>
350
351Both {{length}} and {{length+}} return the length of the argument. It is an
352error to pass a value to {{length}} which is not a proper list (finite and
353nil-terminated). In particular, this means an implementation may diverge or
354signal an error when {{length}} is applied to a circular list.
355
356{{length+}}, on the other hand, returns {{#F}} when applied to a circular
357list.
358
359The length of a proper list is a non-negative integer N such that {{cdr}}
360applied N times to the list produces the empty list.
361
362<procedure>(append! list_1 ...) -> list</procedure><br>
363
364{{append!}} is the "linear-update" variant of {{append}} -- it is allowed,
365but not required, to alter cons cells in the argument lists to construct
366the result list. The last argument is never altered; the result list shares
367structure with this parameter.
368
369<procedure>(concatenate list-of-lists) -> value</procedure><br>
370<procedure>(concatenate! list-of-lists) -> value</procedure><br>
371
372These functions append the elements of their argument together. That is,
373{{concatenate}} returns
374
375
376 (apply append list-of-lists)
377
378or, equivalently,
379
380
381 (reduce-right append '() list-of-lists)
382
383{{concatenate!}} is the linear-update variant, defined in terms of
384{{append!}} instead of {{append}}.
385
386Note that some Scheme implementations do not support passing more than a
387certain number (''e.g.'', 64) of arguments to an n-ary procedure. In these
388implementations, the {{(apply append ...)}} idiom would fail when applied
389to long lists, but {{concatenate}} would continue to function properly.
390
391As with {{append}} and {{append!}}, the last element of the input list may
392be any value at all.
393
394<procedure>(reverse! list) -> list</procedure><br>
395
396{{reverse!}} is the linear-update variant of {{reverse}}. It is permitted,
397but not required, to alter the argument's cons cells to produce the
398reversed list.
399
400<procedure>(append-reverse rev-head tail) -> list</procedure><br>
401<procedure>(append-reverse! rev-head tail) -> list</procedure><br>
402
403{{append-reverse}} returns {{(append (reverse REV-HEAD) TAIL)}}. It is
404provided because it is a common operation -- a common list-processing style
405calls for this exact operation to transfer values accumulated in reverse
406order onto the front of another list, and because the implementation is
407significantly more efficient than the simple composition it replaces. (But
408note that this pattern of iterative computation followed by a reverse can
409frequently be rewritten as a recursion, dispensing with the {{reverse}}
410and {{append-reverse}} steps, and shifting temporary, intermediate storage
411from the heap to the stack, which is typically a win for reasons of cache
412locality and eager storage reclamation.)
413
414{{append-reverse!}} is just the linear-update variant -- it is allowed, but
415not required, to alter REV-HEAD's cons cells to construct the result.
416
417<procedure>(zip clist_1 clist_2 ...) -> list</procedure><br>
418
419
420 (lambda lists (apply map list lists))
421
422If {{zip}} is passed N lists, it returns a list as long as the shortest of
423these lists, each element of which is an N-element list comprised of the
424corresponding elements from the parameter lists.
425
426
427 (zip '(one two three)
428      '(1 2 3)
429      '(odd even odd even odd even odd even))
430     => ((one 1 odd) (two 2 even) (three 3 odd))
431 
432 (zip '(1 2 3)) => ((1) (2) (3))
433
434
435At least one of the argument lists must be finite:
436
437
438 (zip '(3 1 4 1) (circular-list #f #t))
439     => ((3 #f) (1 #t) (4 #f) (1 #t))
440
441<procedure>(unzip1 list) -> list</procedure><br>
442<procedure>(unzip2 list) -> [list list]</procedure><br>
443<procedure>(unzip3 list) -> [list list list]</procedure><br>
444<procedure>(unzip4 list) -> [list list list list]</procedure><br>
445<procedure>(unzip5 list) -> [list list list list list]</procedure><br>
446
447{{unzip1}} takes a list of lists, where every list must contain at least
448one element, and returns a list containing the initial element of each such
449list. That is, it returns {{(map car lists)}}. {{unzip2}} takes a list of
450lists, where every list must contain at least two elements, and returns two
451values: a list of the first elements, and a list of the second elements.
452{{unzip3}} does the same for the first three elements of the lists, and so
453forth.
454
455
456 (unzip2 '((1 one) (2 two) (3 three))) =>
457     (1 2 3)
458     (one two three)
459
460<procedure>(count pred clist_1 clist_2) -> integer</procedure><br>
461
462PRED is a procedure taking as many arguments as there are lists and
463returning a single value. It is applied element-wise to the elements of
464the LISTs, and a count is tallied of the number of elements that produce a
465true value. This count is returned. {{count}} is "iterative" in that it is
466guaranteed to apply PRED to the LIST elements in a left-to-right order. The
467counting stops when the shortest list expires.
468
469
470 (count even? '(3 1 4 1 5 9 2 5 6)) => 3
471 (count < '(1 2 4 8) '(2 4 6 8 10 12 14 16)) => 3
472
473
474At least one of the argument lists must be finite:
475
476
477 (count < '(3 1 4 1) (circular-list 1 10)) => 2
478
479
480==== Fold, unfold & map
481
482<procedure>(fold kons knil clist_1 clist_2 ...) -> value</procedure><br>
483
484The fundamental list iterator.
485
486First, consider the single list-parameter case. If CLIST_1 = (E_1 E_2 ...
487E_N), then this procedure returns
488
489{{(KONS E_N ... (KONS E_2 (KONS E_1 KNIL)) ... )}}
490
491That is, it obeys the (tail) recursion
492
493
494 (fold KONS KNIL LIS) = (fold KONS (KONS (car LIS) KNIL) (cdr LIS))
495 (fold KONS KNIL '()) = KNIL
496
497
498Examples:
499
500
501 (fold + 0 lis)                 ; Add up the elements of LIS.
502 
503 (fold cons '() lis)            ; Reverse LIS.
504 
505 (fold cons tail rev-head)      ; See APPEND-REVERSE.
506 
507 ;; How many symbols in LIS?
508 (fold (lambda (x count) (if (symbol? x) (+ count 1) count))
509       0
510       lis)
511 
512 ;; Length of the longest string in LIS:
513 (fold (lambda (s max-len) (max max-len (string-length s)))
514       0
515       lis)
516
517If N list arguments are provided, then the KONS function must take N+1
518parameters: one element from each list, and the "seed" or fold state, which
519is initially KNIL. The fold operation terminates when the shortest list
520runs out of values:
521
522
523 (fold cons* '() '(a b c) '(1 2 3 4 5)) => (c 3 b 2 a 1)
524
525At least one of the list arguments must be finite.
526
527<procedure>(fold-right kons knil clist_1 clist_2 ...) -> value</procedure><br>
528
529The fundamental list recursion operator.
530
531First, consider the single list-parameter case. If CLIST_1 = {{(E_1 E_2 ...
532E_N)}}, then this procedure returns
533
534{{ (KONS E_1 (KONS E_2 ... (KONS E_N KNIL))) }}
535
536That is, it obeys the recursion
537
538
539 (fold-right KONS KNIL LIS) = (KONS (car LIS) (fold-right KONS KNIL (cdr LIS)))
540 (fold-right KONS KNIL '()) = KNIL
541
542
543Examples:
544
545
546 (fold-right cons '() lis)              ; Copy LIS.
547 
548 ;; Filter the even numbers out of LIS.
549 (fold-right (lambda (x l) (if (even? x) (cons x l) l)) '() lis))
550
551If N list arguments are provided, then the KONS function must take N+1
552parameters: one element from each list, and the "seed" or fold state, which
553is initially KNIL. The fold operation terminates when the shortest list
554runs out of values:
555
556
557 (fold-right cons* '() '(a b c) '(1 2 3 4 5)) => (a 1 b 2 c 3)
558
559At least one of the list arguments must be finite.
560
561<procedure>(pair-fold kons knil clist_1 clist_2 ...) -> value</procedure><br>
562
563Analogous to {{fold}}, but KONS is applied to successive sublists of the
564lists, rather than successive elements -- that is, KONS is applied to the
565pairs making up the lists, giving this (tail) recursion:
566
567
568 (pair-fold KONS KNIL LIS) = (let ((tail (cdr LIS)))
569                               (pair-fold KONS (KONS LIS KNIL) tail))
570 (pair-fold KONS KNIL {{'()}}) = KNIL
571
572
573For finite lists, the KONS function may reliably apply {{set-cdr!}} to the
574pairs it is given without altering the sequence of execution.
575
576Example:
577
578
579 ;;; Destructively reverse a list.
580 (pair-fold (lambda (pair tail) (set-cdr! pair tail) pair) '() lis))
581
582At least one of the list arguments must be finite.
583
584<procedure>(pair-fold-right kons knil clist_1 clist_2 ...) -> value</procedure><br>
585
586Holds the same relationship with {{fold-right}} that {{pair-fold}} holds
587with {{fold}}. Obeys the recursion
588
589
590 (pair-fold-right KONS KNIL LIS) =
591     (KONS LIS (pair-fold-right KONS KNIL (cdr LIS)))
592 (pair-fold-right KONS KNIL {{'()}}) = KNIL
593
594
595Example:
596
597
598 (pair-fold-right cons '() '(a b c)) => ((a b c) (b c) (c))
599
600At least one of the list arguments must be finite.
601
602<procedure>(reduce f ridentity list) -> value</procedure><br>
603
604{{reduce}} is a variant of {{fold}}.
605
606RIDENTITY should be a "right identity" of the procedure F -- that is, for
607any value X acceptable to F,
608
609
610 (F X RIDENTITY) = X
611
612{{reduce}} has the following definition:
613
614If LIST = (), return RIDENTITY; Otherwise, return {{(fold F (car LIST) (cdr
615LIST))}}.
616
617...in other words, we compute {{(fold F RIDENTITY LIST)}}.
618
619Note that RIDENTITY is used ''only'' in the empty-list case. You typically
620use {{reduce}} when applying F is expensive and you'd like to avoid the
621extra application incurred when {{fold}} applies F to the head of LIST
622and the identity value, redundantly producing the same value passed in
623to F. For example, if F involves searching a file directory or performing
624a database query, this can be significant. In general, however, {{fold}}
625is useful in many contexts where {{reduce}} is not (consider the examples
626given in the {{fold}} definition -- only one of the five folds uses a
627function with a right identity. The other four may not be performed with
628{{reduce}}).
629
630Note: MIT Scheme and Haskell flip F's arg order for their {{reduce}} and
631{{fold}} functions.
632
633
634 ;; Take the max of a list of non-negative integers.
635 (reduce max 0 nums) ; i.e., (apply max 0 nums)
636
637<procedure>(reduce-right f ridentity list) -> value</procedure><br>
638
639{{reduce-right}} is the fold-right variant of {{reduce}}. It obeys the
640following definition:
641
642
643 (reduce-right F RIDENTITY '()) = RIDENTITY
644 (reduce-right F RIDENTITY '(E_1)) = (F E_1 RIDENTITY) = E_1
645 
646 (reduce-right F RIDENTITY '(E_1 E_2 ...)) =
647     (F E_1 (reduce F RIDENTITY (E_2 ...)))
648
649
650...in other words, we compute {{(fold-right F RIDENTITY LIST)}}.
651
652
653 ;; Append a bunch of lists together.
654 ;; I.e., (apply append list-of-lists)
655 (reduce-right append '() list-of-lists)
656
657<procedure>(unfold p f g seed [tail-gen]) -> list</procedure><br>
658
659{{unfold}} is best described by its basic recursion:
660
661
662 (unfold P F G SEED) =
663     (if (P SEED) (TAIL-GEN SEED)
664         (cons (F SEED)
665               (unfold P F G (G SEED))))
666
667
668
669; P : Determines when to stop unfolding.
670; F : Maps each seed value to the corresponding list element.
671; G : Maps each seed value to next seed value.
672; SEED : The "state" value for the unfold.
673; TAIL-GEN : Creates the tail of the list; defaults to {{(lambda (x) '())}}
674
675In other words, we use G to generate a sequence of seed values
676
677SEED, G(SEED), G^2(SEED), G^3(SEED), ...
678
679These seed values are mapped to list elements by F, producing the elements
680of the result list in a left-to-right order. P says when to stop.
681
682{{unfold}} is the fundamental recursive list constructor, just as
683{{fold-right}} is the fundamental recursive list consumer. While {{unfold}}
684may seem a bit abstract to novice functional programmers, it can be used in
685a number of ways:
686
687
688 ;; List of squares: 1^2 ... 10^2
689 (unfold (lambda (x) (> x 10))
690         (lambda (x) (* x x))
691        (lambda (x) (+ x 1))
692        1)
693               
694 (unfold null-list? car cdr lis) ; Copy a proper list.
695 
696 ;; Read current input port into a list of values.
697 (unfold eof-object? values (lambda (x) (read)) (read))
698 
699 ;; Copy a possibly non-proper list:
700 (unfold not-pair? car cdr lis
701               values)
702 
703 ;; Append HEAD onto TAIL:
704 (unfold null-list? car cdr head
705               (lambda (x) tail))
706
707Interested functional programmers may enjoy noting that {{fold-right}} and
708{{unfold}} are in some sense inverses. That is, given operations KNULL?,
709KAR, KDR, KONS, and KNIL satisfying
710
711{{(KONS (KAR X) (KDR X))}} = {{x}} and {{(KNULL? KNIL)}} = {{#t}}
712
713then
714
715{{(fold-right KONS KNIL (unfold KNULL? KAR KDR X))}} = X
716
717and
718
719{{(unfold KNULL? KAR KDR (fold-right KONS KNIL X))}} = X.
720
721This combinator sometimes is called an "anamorphism;" when an explicit
722TAIL-GEN procedure is supplied, it is called an "apomorphism."
723
724<procedure>(unfold-right p f g seed [tail]) -> list</procedure><br>
725
726{{unfold-right}} constructs a list with the following loop:
727
728
729 (let lp ((seed seed) (lis tail))
730   (if (p seed) lis
731       (lp (g seed)
732           (cons (f seed) lis))))
733
734
735; P : Determines when to stop unfolding.
736; F : Maps each seed value to the corresponding list element.
737; G : Maps each seed value to next seed value.
738; SEED : The "state" value for the unfold.
739; TAIL : list terminator; defaults to {{'()}}.
740
741In other words, we use G to generate a sequence of seed values
742
743SEED, G(SEED), G^2(SEED), G^3(SEED), ...
744
745These seed values are mapped to list elements by F, producing the elements
746of the result list in a right-to-left order. P says when to stop.
747
748{{unfold-right}} is the fundamental iterative list constructor, just as
749{{fold}} is the fundamental iterative list consumer. While {{unfold-right}}
750may seem a bit abstract to novice functional programmers, it can be used in
751a number of ways:
752
753
754 ;; List of squares: 1^2 ... 10^2
755 (unfold-right zero?
756               (lambda (x) (* x x))
757               (lambda (x) (- x 1))
758               10)
759       
760 ;; Reverse a proper list.
761 (unfold-right null-list? car cdr lis)
762 
763 ;; Read current input port into a list of values.
764 (unfold-right eof-object? values (lambda (x) (read)) (read))
765 
766 ;; (append-reverse rev-head tail)
767 (unfold-right null-list? car cdr rev-head tail)
768
769Interested functional programmers may enjoy noting that {{fold}} and
770{{unfold-right}} are in some sense inverses. That is, given operations
771KNULL?, KAR, KDR, KONS, and KNIL satisfying
772
773{{(KONS (KAR X) (KDR X))}} = {{x}} and {{(KNULL? KNIL)}} = {{#t}}
774
775then
776
777{{(fold KONS KNIL (unfold-right KNULL? KAR KDR X))}} = X
778
779and
780
781{{(unfold-right KNULL? KAR KDR (fold KONS KNIL X))}} = X.
782
783This combinator presumably has some pretentious mathematical name;
784interested readers are invited to communicate it to the author.
785
786<procedure>(map proc clist_1 clist_2 ...) -> list</procedure><br>
787
788This procedure is extended from its R5RS specification to allow the
789arguments to be of unequal length; it terminates when the shortest list
790runs out.
791
792At least one of the argument lists must be finite:
793
794 (map + '(3 1 4 1) (circular-list 1 0)) => (4 1 5 1)
795
796<procedure>(for-each proc clist_1 clist_2 ...) -> unspecified</procedure><br>
797
798This procedure is extended from its R5RS specification to allow the
799arguments to be of unequal length; it terminates when the shortest list
800runs out.
801
802At least one of the argument lists must be finite.
803
804<procedure>(append-map f clist_1 clist_2 ...) -> value</procedure><br>
805<procedure>(append-map! f clist_1 clist_2 ...) -> value</procedure><br>
806
807Equivalent to
808
809{{ (apply append (map F CLIST_1 CLIST_2 ...)) }}
810
811and
812
813{{ (apply append! (map F CLIST_1 CLIST_2 ...)) }}
814
815Map F over the elements of the lists, just as in the {{map}} function.
816However, the results of the applications are appended together to make
817the final result. {{append-map}} uses {{append}} to append the results
818together; {{append-map!}} uses {{append!}}.
819
820The dynamic order in which the various applications of F are made is not
821specified.
822
823Example:
824
825
826 (append-map! (lambda (x) (list x (- x))) '(1 3 8))
827     => (1 -1 3 -3 8 -8)
828
829At least one of the list arguments must be finite.
830
831<procedure>(map! f list_1 clist_2 ...) -> list</procedure><br>
832
833Linear-update variant of {{map}} -- {{map!}} is allowed, but not required,
834to alter the cons cells of LIST_1 to construct the result list.
835
836The dynamic order in which the various applications of F are made is not
837specified. In the n-ary case, CLIST_2, CLIST_3, ... must have at least as
838many elements as LIST_1.
839
840<procedure>(map-in-order f clist_1 clist_2 ...) -> list</procedure><br>
841
842A variant of the {{map}} procedure that guarantees to apply F across the
843elements of the LIST_I arguments in a left-to-right order. This is useful
844for mapping procedures that both have side effects and return useful
845values.
846
847At least one of the list arguments must be finite.
848
849<procedure>(pair-for-each f clist_1 clist_2 ...) -> unspecific</procedure><br>
850
851Like {{for-each}}, but F is applied to successive sublists of the argument
852lists. That is, F is applied to the cons cells of the lists, rather than
853the lists' elements. These applications occur in left-to-right order.
854
855The F procedure may reliably apply {{set-cdr!}} to the pairs it is given
856without altering the sequence of execution.
857
858
859 (pair-for-each (lambda (pair) (display pair) (newline)) '(a b c)) ==>
860     (a b c)
861     (b c)
862     (c)
863
864At least one of the list arguments must be finite.
865
866<procedure>(filter-map f clist_1 clist_2 ...) -> list</procedure><br>
867
868Like {{map}}, but only true values are saved.
869
870
871 (filter-map (lambda (x) (and (number? x) (* x x))) '(a 1 b 3 c 7))
872     => (1 9 49)
873
874The dynamic order in which the various applications of F are made is not
875specified.
876
877At least one of the list arguments must be finite.
878
879
880==== Filtering & partitioning
881
882<procedure>(filter pred list) -> list</procedure><br>
883
884Return all the elements of LIST that satisfy predicate PRED. The list is
885not disordered -- elements that appear in the result list occur in the same
886order as they occur in the argument list. The returned list may share a
887common tail with the argument list. The dynamic order in which the various
888applications of PRED are made is not specified.
889
890
891 (filter even? '(0 7 8 8 43 -4)) => (0 8 8 -4)
892
893<procedure>(partition pred list) -> [list list]</procedure><br>
894
895Partitions the elements of LIST with predicate PRED, and returns two
896values: the list of in-elements and the list of out-elements. The list is
897not disordered -- elements occur in the result lists in the same order as
898they occur in the argument list. The dynamic order in which the various
899applications of PRED are made is not specified. One of the returned lists
900may share a common tail with the argument list.
901
902
903 (partition symbol? '(one 2 3 four five 6)) =>
904     (one four five)
905     (2 3 6)
906
907<procedure>(remove pred list) -> list</procedure><br>
908
909Returns LIST without the elements that satisfy predicate PRED:
910
911
912 (lambda (pred list) (filter (lambda (x) (not (pred x))) list))
913
914The list is not disordered -- elements that appear in the result list occur
915in the same order as they occur in the argument list. The returned list may
916share a common tail with the argument list. The dynamic order in which the
917various applications of PRED are made is not specified.
918
919
920 (remove even? '(0 7 8 8 43 -4)) => (7 43)
921
922<procedure>(filter! pred list) -> list</procedure><br>
923<procedure>(partition! pred list) -> [list list]</procedure><br>
924<procedure>(remove! pred list) -> list</procedure><br>
925
926Linear-update variants of {{filter}}, {{partition}} and {{remove}}. These
927procedures are allowed, but not required, to alter the cons cells in the
928argument list to construct the result lists.
929
930
931==== Searching
932
933The following procedures all search lists for a leftmost element satisfying
934some criteria. This means they do not always examine the entire list;
935thus, there is no efficient way for them to reliably detect and signal an
936error when passed a dotted or circular list. Here are the general rules
937describing how these procedures work when applied to different kinds of
938lists:
939
940
941; Proper lists : The standard, canonical behavior happens in this case.
942; 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 with 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.
943; 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.
944
945Here are some examples, using the {{find}} and {{any}} procedures as
946canonical representatives:
947
948
949 ;; Proper list -- success
950 (find even? '(1 2 3))  => 2
951 (any  even? '(1 2 3))  => #t
952 
953 ;; proper list -- failure
954 (find even? '(1 7 3))  => #f
955 (any  even? '(1 7 3))  => #f
956 
957 ;; Failure is error on a dotted list.
958 (find even? '(1 3 . x))        => error
959 (any  even? '(1 3 . x))        => error
960 
961 ;; The dotted list contains an element satisfying the search.
962 ;; This case is not specified -- it could be success, an error,
963 ;; or some third possibility.
964 (find even? '(1 2 . x))        => error/undefined
965 (any  even? '(1 2 . x))        => error/undefined ; success, error or other.
966 
967 ;; circular list -- success
968 (find even? (circular-list 1 6 3)) => 6
969 (any  even? (circular-list 1 6 3)) => #t
970 
971 ;; circular list -- failure is error. Procedure may diverge.
972 (find even? (circular-list 1 3)) => error
973 (any  even? (circular-list 1 3)) => error
974
975
976<procedure>(find pred clist) -> value</procedure><br>
977
978Return the first element of CLIST that satisfies predicate PRED; false if
979no element does.
980
981
982 (find even? '(3 1 4 1 5 9)) => 4
983
984Note that {{find}} has an ambiguity in its lookup semantics -- if {{find}}
985returns {{#f}}, you cannot tell (in general) if it found a {{#f}} element
986that satisfied PRED, or if it did not find any element at all. In many
987situations, this ambiguity cannot arise -- either the list being searched
988is known not to contain any {{#f}} elements, or the list is guaranteed to
989have an element satisfying PRED. However, in cases where this ambiguity can
990arise, you should use {{find-tail}} instead of {{find}} -- {{find-tail}}
991has no such ambiguity:
992
993
994 (cond ((find-tail pred lis) => (lambda (pair) ...)) ; Handle (CAR PAIR)
995       (else ...)) ; Search failed.
996
997<procedure>(find-tail pred clist) -> pair or false</procedure><br>
998
999Return the first pair of CLIST whose car satisfies PRED. If no pair does,
1000return false.
1001
1002{{find-tail}} can be viewed as a general-predicate variant of the
1003{{member}} function.
1004
1005Examples:
1006
1007
1008 (find-tail even? '(3 1 37 -8 -5 0 0)) => (-8 -5 0 0)
1009 (find-tail even? '(3 1 37 -5)) => #f
1010 
1011 ;; MEMBER X LIS:
1012 (find-tail (lambda (elt) (equal? x elt)) lis)
1013
1014
1015In the circular-list case, this procedure "rotates" the list.
1016
1017{{Find-tail}} is essentially {{drop-while}}, where the sense of the
1018predicate is inverted: {{Find-tail}} searches until it finds an element
1019satisfying the predicate; {{drop-while}} searches until it finds an element
1020that ''doesn't'' satisfy the predicate.
1021
1022<procedure>(take-while pred clist) -> list</procedure><br>
1023<procedure>(take-while! pred clist) -> list</procedure><br>
1024
1025Returns the longest initial prefix of CLIST whose elements all satisfy the
1026predicate PRED.
1027
1028{{Take-while!}} is the linear-update variant. It is allowed, but not
1029required, to alter the argument list to produce the result.
1030
1031
1032 (take-while even? '(2 18 3 10 22 9)) => (2 18)
1033
1034<procedure>(drop-while pred clist) -> list</procedure><br>
1035
1036Drops the longest initial prefix of CLIST whose elements all satisfy the
1037predicate PRED, and returns the rest of the list.
1038
1039
1040 (drop-while even? '(2 18 3 10 22 9)) => (3 10 22 9)
1041
1042
1043The circular-list case may be viewed as "rotating" the list.
1044
1045<procedure>(span pred clist) -> [list clist]</procedure><br>
1046<procedure>(span! pred list) -> [list list]</procedure><br>
1047<procedure>(break pred clist) -> [list clist]</procedure><br>
1048<procedure>(break! pred list) -> [list list]</procedure><br>
1049
1050{{Span}} splits the list into the longest initial prefix whose elements all
1051satisfy PRED, and the remaining tail. {{Break}} inverts the sense of the
1052predicate: the tail commences with the first element of the input list that
1053satisfies the predicate.
1054
1055In other words: {{span}} finds the intial span of elements satisfying PRED,
1056and {{break}} breaks the list at the first element satisfying PRED.
1057
1058{{Span}} is equivalent to
1059
1060
1061 (values (take-while PRED CLIST)
1062         (drop-while PRED CLIST))
1063
1064{{Span!}} and {{break!}} are the linear-update variants. They are allowed,
1065but not required, to alter the argument list to produce the result.
1066
1067
1068 (span even? '(2 18 3 10 22 9)) =>
1069   (2 18)
1070   (3 10 22 9)
1071 
1072 (break even? '(3 1 4 1 5 9)) =>
1073   (3 1)
1074   (4 1 5 9)
1075
1076<procedure>(any pred clist_1 clist_2 ...) -> value</procedure><br>
1077
1078Applies the predicate across the lists, returning true if the predicate
1079returns true on any application.
1080
1081If there are N list arguments CLIST_1 ... CLIST_N, then PRED must be a
1082procedure taking N arguments and returning a boolean result.
1083
1084{{any}} applies PRED to the first elements of the CLIST_I parameters. If
1085this application returns a true value, {{any}} immediately returns that
1086value. Otherwise, it iterates, applying PRED to the second elements of the
1087CLIST_I parameters, then the third, and so forth. The iteration stops when
1088a true value is produced or one of the lists runs out of values; in the
1089latter case, {{any}} returns {{#f}}. The application of PRED to the last
1090element of the lists is a tail call.
1091
1092Note the difference between {{find}} and {{any}} -- {{find}} returns the
1093element that satisfied the predicate; {{any}} returns the true value that
1094the predicate produced.
1095
1096Like {{every}}, {{any}}'s name does not end with a question mark -- this
1097is to indicate that it does not return a simple boolean ({{#t}} or {{#f}}),
1098but a general value.
1099
1100
1101 (any integer? '(a 3 b 2.7))   => #t
1102 (any integer? '(a 3.1 b 2.7)) => #f
1103 (any < '(3 1 4 1 5)
1104        '(2 7 1 8 2)) => #t
1105
1106<procedure>(every pred clist_1 clist_2 ...) -> value</procedure><br>
1107
1108Applies the predicate across the lists, returning true if the predicate
1109returns true on every application.
1110
1111If there are N list arguments CLIST_1 ... CLIST_N, then PRED must be a
1112procedure taking N arguments and returning a boolean result.
1113
1114{{every}} applies PRED to the first elements of the CLIST_I parameters.
1115If this application returns false, {{every}} immediately returns false.
1116Otherwise, it iterates, applying PRED to the second elements of the CLIST_I
1117parameters, then the third, and so forth. The iteration stops when a false
1118value is produced or one of the lists runs out of values. In the latter
1119case, {{every}} returns the true value produced by its final application
1120of PRED. The application of PRED to the last element of the lists is a tail
1121call.
1122
1123If one of the CLIST_I has no elements, {{every}} simply returns {{#t}}.
1124
1125Like {{any}}, {{every}}'s name does not end with a question mark -- this
1126is to indicate that it does not return a simple boolean ({{#t}} or {{#f}}),
1127but a general value.
1128
1129<procedure>(list-index pred clist_1 clist_2 ...) -> integer or false</procedure><br>
1130
1131Return the index of the leftmost element that satisfies PRED.
1132
1133If there are N list arguments CLIST_1 ... CLIST_N, then PRED must be a
1134function taking N arguments and returning a boolean result.
1135
1136{{list-index}} applies PRED to the first elements of the CLIST_I
1137parameters. If this application returns true, {{list-index}} immediately
1138returns zero. Otherwise, it iterates, applying PRED to the second elements
1139of the CLIST_I parameters, then the third, and so forth. When it finds a
1140tuple of list elements that cause PRED to return true, it stops and returns
1141the zero-based index of that position in the lists.
1142
1143The iteration stops when one of the lists runs out of values; in this case,
1144{{list-index}} returns {{#f}}.
1145
1146
1147 (list-index even? '(3 1 4 1 5 9)) => 2
1148 (list-index < '(3 1 4 1 5 9 2 5 6) '(2 7 1 8 2)) => 1
1149 (list-index = '(3 1 4 1 5 9 2 5 6) '(2 7 1 8 2)) => #f
1150
1151
1152<procedure>(member x list [=]) -> list</procedure><br>
1153
1154{{member}} is extended from its R5RS definition to allow the client to pass
1155in an optional equality procedure = used to compare keys.
1156
1157The comparison procedure is used to compare the elements E_I of LIST to the
1158key X in this way:
1159
1160{{ (= X E_I) ; list is (E1 ... En) }}
1161
1162That is, the first argument is always X, and the second argument is one
1163of the list elements. Thus one can reliably find the first element of LIST
1164that is greater than five with {{(member 5 LIST <)}}
1165
1166Note that fully general list searching may be performed with the
1167{{find-tail}} and {{find}} procedures, ''e.g.''
1168
1169
1170 (find-tail even? list) ; Find the first elt with an even key.
1171
1172
1173==== Deletion
1174
1175<procedure>(delete x list [=]) -> list</procedure><br>
1176<procedure>(delete! x list [=]) -> list</procedure><br>
1177
1178{{delete}} uses the comparison procedure =, which defaults to {{equal?}},
1179to find all elements of LIST that are equal to X, and deletes them from
1180LIST. The dynamic order in which the various applications of = are made is
1181not specified.
1182
1183The list is not disordered -- elements that appear in the result list occur
1184in the same order as they occur in the argument list. The result may share
1185a common tail with the argument list.
1186
1187Note that fully general element deletion can be performed with the
1188{{remove}} and {{remove!}} procedures, ''e.g.'':
1189
1190
1191 ;; Delete all the even elements from LIS:
1192 (remove even? lis)
1193
1194The comparison procedure is used in this way: {{(= X E_I)}}. That is,
1195X is always the first argument, and a list element is always the second
1196argument. The comparison procedure will be used to compare each element of
1197LIST exactly once; the order in which it is applied to the various E_I is
1198not specified. Thus, one can reliably remove all the numbers greater than
1199five from a list with {{(delete 5 list <)}}
1200
1201{{delete!}} is the linear-update variant of {{delete}}. It is allowed, but
1202not required, to alter the cons cells in its argument list to construct the
1203result.
1204
1205<procedure>(delete-duplicates list [=]) -> list</procedure><br>
1206<procedure>(delete-duplicates! list [=]) -> list</procedure><br>
1207
1208{{delete-duplicates}} removes duplicate elements from the list argument.
1209If there are multiple equal elements in the argument list, the result list
1210only contains the first or leftmost of these elements in the result. The
1211order of these surviving elements is the same as in the original list --
1212{{delete-duplicates}} does not disorder the list (hence it is useful for
1213"cleaning up" association lists).
1214
1215The = parameter is used to compare the elements of the list; it defaults to
1216{{equal?}}. If X comes before Y in LIST, then the comparison is performed
1217{{(= X Y)}}. The comparison procedure will be used to compare each pair of
1218elements in LIST no more than once; the order in which it is applied to the
1219various pairs is not specified.
1220
1221Implementations of {{delete-duplicates}} are allowed to share common tails
1222between argument and result lists -- for example, if the list argument
1223contains only unique elements, it may simply return exactly this list.
1224
1225Be aware that, in general, {{delete-duplicates}} runs in time O(n^2) for
1226N-element lists. Uniquifying long lists can be accomplished in O(n lg n)
1227time by sorting the list to bring equal elements together, then using a
1228linear-time algorithm to remove equal elements. Alternatively, one can use
1229algorithms based on element-marking, with linear-time results.
1230
1231{{delete-duplicates!}} is the linear-update variant of
1232{{delete-duplicates}}; it is allowed, but not required, to alter the cons
1233cells in its argument list to construct the result.
1234
1235
1236 (delete-duplicates '(a b a c a b c z)) => (a b c z)
1237 
1238 ;; Clean up an alist:
1239 (delete-duplicates '((a . 3) (b . 7) (a . 9) (c . 1))
1240                    (lambda (x y) (eq? (car x) (car y))))
1241     => ((a . 3) (b . 7) (c . 1))
1242
1243
1244==== Association lists
1245
1246An "association list" (or "alist") is a list of pairs. The car of each
1247pair contains a key value, and the cdr contains the associated data value.
1248They can be used to construct simple look-up tables in Scheme. Note that
1249association lists are probably inappropriate for performance-critical use
1250on large data; in these cases, hash tables or some other alternative should
1251be employed.
1252
1253<procedure>(assoc key alist [=]) -> pair or #f</procedure><br>
1254
1255{{assoc}} is extended from its R5RS definition to allow the client to pass
1256in an optional equality procedure = used to compare keys.
1257
1258The comparison procedure is used to compare the elements E_I of LIST to the
1259KEY parameter in this way:
1260
1261{{ (= KEY (car E_I)) ; list is (E1 ... En) }}
1262
1263That is, the first argument is always KEY, and the second argument is one
1264of the list elements. Thus one can reliably find the first entry of ALIST
1265whose key is greater than five with {{(assoc 5 ALIST <)}}
1266
1267Note that fully general alist searching may be performed with the
1268{{find-tail}} and {{find}} procedures, ''e.g.''
1269
1270
1271 ;; Look up the first association in ALIST with an even key:
1272 (find (lambda (a) (even? (car a))) alist)
1273
1274<procedure>(alist-cons key datum alist) -> alist</procedure><br>
1275
1276
1277 (lambda (key datum alist) (cons (cons key datum) alist))
1278
1279Cons a new alist entry mapping KEY -> DATUM onto ALIST.
1280
1281<procedure>(alist-copy alist) -> alist</procedure><br>
1282
1283Make a fresh copy of ALIST. This means copying each pair that forms an
1284association as well as the spine of the list, ''i.e.''
1285
1286
1287 (lambda (a) (map (lambda (elt) (cons (car elt) (cdr elt))) a))
1288
1289
1290<procedure>(alist-delete key alist [=]) -> alist</procedure><br>
1291<procedure>(alist-delete! key alist [=]) -> alist</procedure><br>
1292
1293{{alist-delete}} deletes all associations from ALIST with the given KEY,
1294using key-comparison procedure =, which defaults to {{equal?}}. The dynamic
1295order in which the various applications of = are made is not specified.
1296
1297Return values may share common tails with the ALIST argument. The alist
1298is not disordered -- elements that appear in the result alist occur in the
1299same order as they occur in the argument alist.
1300
1301The comparison procedure is used to compare the element keys K_I of ALIST's
1302entries to the KEY parameter in this way: {{(= KEY K_I)}}. Thus, one can
1303reliably remove all entries of ALIST whose key is greater than five with
1304{{(alist-delete 5 ALIST <)}}
1305
1306{{alist-delete!}} is the linear-update variant of {{alist-delete}}. It is
1307allowed, but not required, to alter cons cells from the ALIST parameter to
1308construct the result.
1309
1310
1311==== Set operations on lists
1312
1313These procedures implement operations on sets represented as lists of
1314elements. They all take an = argument used to compare elements of lists.
1315This equality procedure is required to be consistent with {{eq?}}. That is,
1316it must be the case that
1317
1318{{(eq? X Y)}} => {{(= X Y)}}.
1319
1320Note that this implies, in turn, that two lists that are {{eq?}} are also
1321set-equal by any legal comparison procedure. This allows for constant-time
1322determination of set operations on {{eq?}} lists.
1323
1324Be aware that these procedures typically run in time O(N * M) for N- and
1325M-element list arguments. Performance-critical applications operating upon
1326large sets will probably wish to use other data structures and algorithms.
1327
1328<procedure>(lset<= = list_1 ...) -> boolean</procedure><br>
1329
1330Returns true iff every LIST_I is a subset of LIST_I+1, using = for the
1331element-equality procedure. List A is a subset of list B if every element
1332in A is equal to some element of B. When performing an element comparison,
1333the = procedure's first argument is an element of A; its second, an element
1334of B.
1335
1336
1337 (lset<= eq? '(a) '(a b a) '(a b c c)) => #t
1338 
1339 (lset<= eq?) => #t             ; Trivial cases
1340 (lset<= eq? '(a)) => #t
1341
1342<procedure>(lset= = list_1 list_2 ...) -> boolean</procedure><br>
1343
1344Returns true iff every LIST_I is set-equal to LIST_I+1, using = for the
1345element-equality procedure. "Set-equal" simply means that LIST_I is a
1346subset of LIST_I+1, and LIST_I+1 is a subset of LIST_I. The = procedure's
1347first argument is an element of LIST_I; its second is an element of
1348LIST_I+1.
1349
1350
1351 (lset= eq? '(b e a) '(a e b) '(e e b a)) => #t
1352 
1353 (lset= eq?) => #t               ; Trivial cases
1354 (lset= eq? '(a)) => #t
1355
1356<procedure>(lset-adjoin = list elt_1 ...) -> list</procedure><br>
1357
1358Adds the ELT_I elements not already in the list parameter to the result
1359list. The result shares a common tail with the list parameter. The new
1360elements are added to the front of the list, but no guarantees are made
1361about their order. The = parameter is an equality procedure used to
1362determine if an ELT_I is already a member of LIST. Its first argument is an
1363element of LIST; its second is one of the ELT_I.
1364
1365The list parameter is always a suffix of the result -- even if the list
1366parameter contains repeated elements, these are not reduced.
1367
1368
1369 (lset-adjoin eq? '(a b c d c e) 'a 'e 'i 'o 'u) => (u o i a b c d c e)
1370
1371<procedure>(lset-union = list_1 ...) -> list</procedure><br>
1372
1373Returns the union of the lists, using = for the element-equality procedure.
1374
1375The union of lists A and B is constructed as follows:
1376
1377
1378* If A is the empty list, the answer is B (or a copy of B).
1379* Otherwise, the result is initialised to be list A (or a copy of A).
1380* Proceed through the elements of list B in a left-to-right order. If B is such an element of B, compare every element R of the current result list to B: {{(= R B)}}. If all comparisons fail, B is consed onto the front of the result.
1381
1382However, there is no guarantee that = will be applied to every pair of
1383arguments from A and B. In particular, if A is {{eq}}? to B, the operation
1384may immediately terminate.
1385
1386In the n-ary case, the two-argument list-union operation is simply folded
1387across the argument lists.
1388
1389
1390 (lset-union eq? '(a b c d e) '(a e i o u)) =>
1391     (u o i a b c d e)
1392 
1393 ;; Repeated elements in LIST1 are preserved.
1394 (lset-union eq? '(a a c) '(x a x)) => (x a a c)
1395 
1396 ;; Trivial cases
1397 (lset-union eq?) => ()
1398 (lset-union eq? '(a b c)) => (a b c)
1399
1400<procedure>(lset-intersection = list_1 list_2 ...) -> list</procedure><br>
1401
1402Returns the intersection of the lists, using = for the element-equality
1403procedure.
1404
1405The intersection of lists A and B is comprised of every element of A that
1406is = to some element of B: {{(= A B)}}, for A in A, and B in B. Note this
1407implies that an element which appears in B and multiple times in list A
1408will also appear multiple times in the result.
1409
1410The order in which elements appear in the result is the same as they appear
1411in LIST_1 -- that is, {{lset-intersection}} essentially filters LIST_1,
1412without disarranging element order. The result may share a common tail with
1413LIST_1.
1414
1415In the n-ary case, the two-argument list-intersection operation is simply
1416folded across the argument lists. However, the dynamic order in which the
1417applications of = are made is not specified. The procedure may check an
1418element of LIST_1 for membership in every other list before proceeding to
1419consider the next element of LIST_1, or it may completely intersect LIST_1
1420and LIST_2 before proceeding to LIST_3, or it may go about its work in some
1421third order.
1422
1423
1424 (lset-intersection eq? '(a b c d e) '(a e i o u)) => (a e)
1425 
1426 ;; Repeated elements in LIST1 are preserved.
1427 (lset-intersection eq? '(a x y a) '(x a x z)) => '(a x a)
1428 
1429 (lset-intersection eq? '(a b c)) => (a b c)     ; Trivial case
1430
1431<procedure>(lset-difference = list_1 list_2 ...) -> list</procedure><br>
1432
1433Returns the difference of the lists, using = for the element-equality
1434procedure -- all the elements of LIST_1 that are not = to any element from
1435one of the other LIST_I parameters.
1436
1437The = procedure's first argument is always an element of LIST_1; its
1438second is an element of one of the other LIST_I. Elements that are repeated
1439multiple times in the LIST_1 parameter will occur multiple times in the
1440result. The order in which elements appear in the result is the same as
1441they appear in LIST_1 -- that is, {{lset-difference}} essentially filters
1442LIST_1, without disarranging element order. The result may share a common
1443tail with LIST_1. The dynamic order in which the applications of = are
1444made is not specified. The procedure may check an element of LIST_1 for
1445membership in every other list before proceeding to consider the next
1446element of LIST_1, or it may completely compute the difference of LIST_1
1447and LIST_2 before proceeding to LIST_3, or it may go about its work in some
1448third order.
1449
1450
1451 (lset-difference eq? '(a b c d e) '(a e i o u)) => (b c d)
1452 
1453 (lset-difference eq? '(a b c)) => (a b c) ; Trivial case
1454
1455
1456<procedure>(lset-xor = list_1 ...) -> list</procedure><br>
1457
1458Returns the exclusive-or of the sets, using = for the element-equality
1459procedure. If there are exactly two lists, this is all the elements that
1460appear in exactly one of the two lists. The operation is associative, and
1461thus extends to the n-ary case -- the elements that appear in an odd number
1462of the lists. The result may share a common tail with any of the LIST_I
1463parameters.
1464
1465More precisely, for two lists A and B, A xor B is a list of
1466
1467
1468* every element A of A such that there is no element B of B such that {{(= A B)}}, and
1469* every element B of B such that there is no element A of A such that {{(= B A)}}.
1470
1471However, an implementation is allowed to assume that = is symmetric -- that
1472is, that
1473
1474{{(= A B)}} => {{(= B A)}}.
1475
1476This means, for example, that if a comparison {{(= A B)}} produces true for
1477some A in A and B in B, both A and B may be removed from inclusion in the
1478result.
1479
1480In the n-ary case, the binary-xor operation is simply folded across the
1481lists.
1482
1483
1484 (lset-xor eq? '(a b c d e) '(a e i o u)) => (d c b i o u)
1485 
1486 ;; Trivial cases.
1487 (lset-xor eq?) => ()
1488 (lset-xor eq? '(a b c d e)) => (a b c d e)
1489
1490<procedure>(lset-diff+intersection = list_1 list_2 ...) -> [list list]</procedure><br>
1491
1492Returns two values -- the difference and the intersection of the lists. Is
1493equivalent to
1494
1495
1496 (values (lset-difference = LIST_1 LIST_2 ...)
1497         (lset-intersection = LIST_1
1498                              (lset-union = LIST_2 ...)))
1499
1500but can be implemented more efficiently.
1501
1502The = procedure's first argument is an element of LIST_1; its second is an
1503element of one of the other LIST_I.
1504
1505Either of the answer lists may share a common tail with LIST_1. This
1506operation essentially partitions LIST_1.
1507
1508<procedure>(lset-union! = list_1 ...) -> list</procedure><br>
1509<procedure>(lset-intersection! = list_1 list_2 ...) -> list</procedure><br>
1510<procedure>(lset-difference! = list_1 list_2 ...) -> list</procedure><br>
1511<procedure>(lset-xor! = list_1 ...) -> list</procedure><br>
1512<procedure>(lset-diff+intersection! = list_1 list_2 ...) -> [list list]</procedure><br>
1513
1514These are linear-update variants. They are allowed, but not required, to
1515use the cons cells in their first list parameter to construct their answer.
1516{{lset-union!}} is permitted to recycle cons cells from ''any'' of its list
1517arguments.
1518
1519
1520=== Author
1521
1522The SRFI-1 library author is Olin Shivers.  The CHICKEN extension is
1523maintained by the CHICKEN Team.
1524
1525
1526=== License
1527
1528  Copyright (c) 1998, 1999 by Olin Shivers. You may do as you please with
1529  this code as long as you do not remove this copyright notice or
1530  hold me liable for its use. Please send bug reports to shivers@ai.mit.edu.
1531
1532
1533=== Version History
1534
1535; 0.4 : Fix missing test dependency on the test egg
1536; 0.3 : Fix test dependencies.
1537; 0.2 : Compile with similar performance options as in CHICKEN 4.
1538; 0.1 : Taken from the srfi-1 core library unit and released as an egg for CHICKEN 5.
Note: See TracBrowser for help on using the repository browser.