source: project/wiki/man/4/Unit srfi-1 @ 25875

Last change on this file since 25875 was 25875, checked in by felix winkelmann, 9 years ago

merged some manual changes from master into wiki

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