Debian Codegraph @

libsrc/scheme/list.scm

raw
1 ;;;
2 ;;; scheme.list - List processing library (R7RS Red)
3 ;;;
4
5 ;; Originally SRFI-1
6
7 ;; This code is based on the reference implementation by Olin Shivers
8 ;;
9 ;; Copyright (c) 1998, 1999 by Olin Shivers. You may do as you please with
10 ;; this code as long as you do not remove this copyright notice or
11 ;; hold me liable for its use. Please send bug reports to [email protected].
12
13 ;; [SK] I added module stuff, deleted procedures that are supported
14 ;; by Gauche core, and tweaked some functions that works well in Gauche.
15 ;; You can obtain the original version from http://srfi.schemers.org
16 ;; NB: Gauche 0.8.5 and before included some optional procedures (such
17 ;; as fold$) in SRFI-1 module. As of 0.8.6, they're moved to gauche.procedure,
18 ;; which is autoloaded. The user doesn't need to see this change.
19
20 (define-module scheme.list
21 ;; The export list includes the procedures defined in #<module gauche>
22 ;; in order to make (import (srfi 1)) work for r7rs programs.
23 (export cons list xcons cons* make-list list-tabulate
24 list-copy circular-list iota
25 pair? null? proper-list? circular-list? dotted-list?
26 not-pair? null-list? list=
27 car cdr caar cadr cdar cddr caaar caadr cadar caddr
28 cdaar cdadr cddar cdddr caaaar caaadr caadar caaddr
29 cadaar cadadr caddar cadddr cdaaar cdaadr cdadar cdaddr
30 cddaar cddadr cdddar cddddr list-ref
31 first second third fourth fifth sixth seventh eighth ninth tenth
32 car+cdr take drop take-right drop-right
33 take! drop-right! split-at split-at! last last-pair
34 length length+ append concatenate reverse
35 append! concatenate! reverse!
36 append-reverse append-reverse!
37 zip unzip1 unzip2 unzip3 unzip4 unzip5 count
38 ;; See https://github.com/shirok/Gauche/issues/957
39 ;; map for-each
40 fold unfold pair-fold reduce fold-right unfold-right
41 pair-fold-right reduce-right append-map append-map!
42 map! pair-for-each filter-map map-in-order
43 filter partition remove filter! partition! remove!
44 member memq memv find find-tail any every list-index
45 take-while drop-while
46 take-while! span break span! break!
47 delete delete-duplicates delete! delete-duplicates!
48 assoc assq assv alist-cons alist-copy alist-delete alist-delete!
49 lset<= lset= lset-adjoin lset-union lset-union!
50 lset-intersection lset-intersection! lset-difference
51 lset-difference! lset-xor lset-xor!
52 lset-diff+intersection lset-diff+intersection!
53 set-car! set-cdr!
54 ))
55 (select-module scheme.list)
56
57 (define (xcons a b) (cons b a))
58
59 (define-inline (not-pair? x) (not (pair? x)))
60
61 ;;;
62 ;;; List generators of SRFI-1
63 ;;;
64
65 ;;; Make a list of length LEN. Elt i is (PROC i) for 0 <= i < LEN.
66 (define (list-tabulate len proc)
67 (check-arg (^n (and (integer? n) (>= n 0))) len)
68 (do ((i (- len 1) (- i 1))
69 (ans '() (cons (proc i) ans)))
70 ((< i 0) ans)))
71
72 (define (circular-list val1 . vals)
73 (let ((ans (cons val1 vals)))
74 (set-cdr! (last-pair ans) ans)
75 ans))
76
77 ;;;
78 ;;; List predicates of SRFI-1
79 ;;;
80
81 (define (list= = . lists)
82 (or (null? lists) ; special case
83
84 (let lp1 ((list-a (car lists))
85 (others (cdr lists)))
86 (or (null? others)
87 (let ((list-b (car others))
88 (others (cdr others)))
89 (if (eq? list-a list-b) ; EQ? => LIST=
90 (lp1 list-b others)
91 (let lp2 ((list-a list-a) (list-c list-b))
92 (if (null-list? list-a)
93 (and (null-list? list-c)
94 (lp1 list-b others))
95 (and (not (null-list? list-c))
96 (= (car list-a) (car list-c))
97 (lp2 (cdr list-a) (cdr list-c)))))))))))
98
99
100 ;;;
101 ;;; Zipper and unzipper of SRFI-1
102 ;;;
103
104 (define (zip list1 . more-lists) (apply map list list1 more-lists))
105
106 (define (unzip1 lis) (map car lis))
107
108 (define (unzip2 lis)
109 (let recur ((lis lis))
110 (if (null-list? lis) (values lis lis) ; Use NOT-PAIR? to handle
111 (let ((elt (car lis))) ; dotted lists.
112 (receive (a b) (recur (cdr lis))
113 (values (cons (car elt) a)
114 (cons (cadr elt) b)))))))
115
116 (define (unzip3 lis)
117 (let recur ((lis lis))
118 (if (null-list? lis) (values lis lis lis)
119 (let ((elt (car lis)))
120 (receive (a b c) (recur (cdr lis))
121 (values (cons (car elt) a)
122 (cons (cadr elt) b)
123 (cons (caddr elt) c)))))))
124
125 (define (unzip4 lis)
126 (let recur ((lis lis))
127 (if (null-list? lis) (values lis lis lis lis)
128 (let ((elt (car lis)))
129 (receive (a b c d) (recur (cdr lis))
130 (values (cons (car elt) a)
131 (cons (cadr elt) b)
132 (cons (caddr elt) c)
133 (cons (cadddr elt) d)))))))
134
135 (define (unzip5 lis)
136 (let recur ((lis lis))
137 (if (null-list? lis) (values lis lis lis lis lis)
138 (let ((elt (car lis)))
139 (receive (a b c d e) (recur (cdr lis))
140 (values (cons (car elt) a)
141 (cons (cadr elt) b)
142 (cons (caddr elt) c)
143 (cons (cadddr elt) d)
144 (cons (car (cddddr elt)) e)))))))
145
146 ;;;
147 ;;; N-th functions of SRFI-1
148 ;;;
149
150 (define first car)
151 (define second cadr)
152 (define third caddr)
153 (define fourth cadddr)
154 (define (fifth x) (car (cddddr x)))
155 (define (sixth x) (cadr (cddddr x)))
156 (define (seventh x) (caddr (cddddr x)))
157 (define (eighth x) (cadddr (cddddr x)))
158 (define (ninth x) (car (cddddr (cddddr x))))
159 (define (tenth x) (cadr (cddddr (cddddr x))))
160
161 ;;;
162 ;;; Utility functions for n-ary operation in SRFI-1
163 ;;;
164
165 (define (car+cdr pair) (values (car pair) (cdr pair)))
166
167 ;;; Return (map cdr lists).
168 ;;; However, if any element of LISTS is empty, just abort and return '().
169 (define (%cdrs lists)
170 (call-with-current-continuation
171 (lambda (abort)
172 (let recur ((lists lists))
173 (if (pair? lists)
174 (let ((lis (car lists)))
175 (if (null-list? lis) (abort '())
176 (cons (cdr lis) (recur (cdr lists)))))
177 '())))))
178
179 (define (%cars+ lists last-elt) ; (append! (map car lists) (list last-elt))
180 (let recur ((lists lists))
181 (if (pair? lists) (cons (caar lists) (recur (cdr lists))) (list last-elt))))
182
183 ;;; LISTS is a (not very long) non-empty list of lists.
184 ;;; Return two lists: the cars & the cdrs of the lists.
185 ;;; However, if any of the lists is empty, just abort and return [() ()].
186
187 (define (%cars+cdrs lists)
188 (call-with-current-continuation
189 (lambda (abort)
190 (let recur ((lists lists))
191 (if (pair? lists)
192 (receive (list other-lists) (car+cdr lists)
193 (if (null-list? list) (abort '() '()) ; LIST is empty -- bail out
194 (receive (a d) (car+cdr list)
195 (receive (cars cdrs) (recur other-lists)
196 (values (cons a cars) (cons d cdrs))))))
197 (values '() '()))))))
198
199 ;;; Like %CARS+CDRS, but blow up if any list is empty.
200 (define (%cars+cdrs/no-test lists)
201 (let recur ((lists lists))
202 (if (pair? lists)
203 (receive (list other-lists) (car+cdr lists)
204 (receive (a d) (car+cdr list)
205 (receive (cars cdrs) (recur other-lists)
206 (values (cons a cars) (cons d cdrs)))))
207 (values '() '()))))
208
209 ;;;
210 ;;; Folders of SRFI-1
211 ;;;
212
213 (define (unfold-right p f g seed :optional (ans '()))
214 (let lp ((seed seed) (ans ans))
215 (if (p seed)
216 ans
217 (lp (g seed)
218 (cons (f seed) ans)))))
219
220
221 (define (unfold p f g seed . maybe-tail-gen)
222 (if (pair? maybe-tail-gen)
223
224 (let ((tail-gen (car maybe-tail-gen)))
225 (if (pair? (cdr maybe-tail-gen))
226 (apply error "Too many arguments" unfold p f g seed maybe-tail-gen)
227
228 (let recur ((seed seed))
229 (if (p seed) (tail-gen seed)
230 (cons (f seed) (recur (g seed)))))))
231
232 (let recur ((seed seed))
233 (if (p seed) '()
234 (cons (f seed) (recur (g seed)))))))
235
236 (define (pair-fold-right f zero lis1 . lists)
237 (if (pair? lists)
238 (let recur ((lists (cons lis1 lists))) ; N-ary case
239 (let ((cdrs (%cdrs lists)))
240 (if (null? cdrs) zero
241 (apply f (append! lists (list (recur cdrs)))))))
242
243 (let recur ((lis lis1)) ; Fast path
244 (if (null-list? lis) zero (f lis (recur (cdr lis)))))))
245
246 (define (pair-fold f zero lis1 . lists)
247 (if (pair? lists)
248 (let lp ((lists (cons lis1 lists)) (ans zero)) ; N-ary case
249 (let ((tails (%cdrs lists)))
250 (if (null? tails) ans
251 (lp tails (apply f (append! lists (list ans)))))))
252
253 (let lp ((lis lis1) (ans zero))
254 (if (null-list? lis) ans
255 (let ((tail (cdr lis))) ; Grab the cdr now,
256 (lp tail (f lis ans))))))) ; in case F SET-CDR!s LIS.
257
258 ;;;
259 ;;; Mapper of SRFI-1
260 ;;;
261
262 (define (pair-for-each proc lis1 . lists)
263 (if (pair? lists)
264
265 (let lp ((lists (cons lis1 lists)))
266 (let ((tails (%cdrs lists)))
267 (if (pair? tails)
268 (begin (apply proc lists)
269 (lp tails)))))
270
271 ;; Fast path.
272 (let lp ((lis lis1))
273 (if (not (null-list? lis))
274 (let ((tail (cdr lis))) ; Grab the cdr now,
275 (proc lis) ; in case PROC SET-CDR!s LIS.
276 (lp tail))))))
277
278 ;;; We stop when LIS1 runs out, not when any list runs out.
279 (define (map! f lis1 . lists)
280 (if (pair? lists)
281 (let lp ((lis1 lis1) (lists lists))
282 (if (not (null-list? lis1))
283 (receive (heads tails) (%cars+cdrs/no-test lists)
284 (set-car! lis1 (apply f (car lis1) heads))
285 (lp (cdr lis1) tails))))
286
287 ;; Fast path.
288 (pair-for-each (lambda (pair) (set-car! pair (f (car pair)))) lis1))
289 lis1)
290
291 ;;;
292 ;;; Filters of SRFI-1
293 ;;;
294
295 (define (partition! pred lis)
296 (check-arg procedure? pred)
297 (if (null-list? lis) (values lis lis)
298
299 ;; This pair of loops zips down contiguous in & out runs of the
300 ;; list, splicing the runs together. The invariants are
301 ;; SCAN-IN: (cdr in-prev) = LIS.
302 ;; SCAN-OUT: (cdr out-prev) = LIS.
303 (letrec ((scan-in (lambda (in-prev out-prev lis)
304 (let lp ((in-prev in-prev) (lis lis))
305 (if (pair? lis)
306 (if (pred (car lis))
307 (lp lis (cdr lis))
308 (begin (set-cdr! out-prev lis)
309 (scan-out in-prev lis (cdr lis))))
310 (set-cdr! out-prev lis))))) ; Done.
311
312 (scan-out (lambda (in-prev out-prev lis)
313 (let lp ((out-prev out-prev) (lis lis))
314 (if (pair? lis)
315 (if (pred (car lis))
316 (begin (set-cdr! in-prev lis)
317 (scan-in lis out-prev (cdr lis)))
318 (lp lis (cdr lis)))
319 (set-cdr! in-prev lis)))))) ; Done.
320
321 ;; Crank up the scan&splice loops.
322 (if (pred (car lis))
323 ;; LIS begins in-list. Search for out-list's first pair.
324 (let lp ((prev-l lis) (l (cdr lis)))
325 (cond ((null-list? l) (values lis l))
326 ((pred (car l)) (lp l (cdr l)))
327 (else (scan-out prev-l l (cdr l))
328 (values lis l)))) ; Done.
329
330 ;; LIS begins out-list. Search for in-list's first pair.
331 (let lp ((prev-l lis) (l (cdr lis)))
332 (cond ((null-list? l) (values l lis))
333 ((pred (car l))
334 (scan-in l prev-l (cdr l))
335 (values l lis)) ; Done.
336 (else (lp l (cdr l)))))))))
337
338 ;;;
339 ;;; Find and alike of SRFI-1
340 ;;;
341
342 ;; use tail-recursion
343 (define (take-while pred lis)
344 (let recur ((lis lis)
345 (r '()))
346 (if (null-list? lis)
347 (reverse! r)
348 (if (pred (car lis))
349 (recur (cdr lis) (cons (car lis) r))
350 (reverse! r)))))
351
352 (define (drop-while pred lis)
353 (let lp ((lis lis))
354 (if (null-list? lis)
355 '()
356 (if (pred (car lis))
357 (lp (cdr lis))
358 lis))))
359
360 (define (take-while! pred lis)
361 (if (or (null-list? lis)
362 (not (pred (car lis))))
363 '()
364 (begin (let lp ((prev lis) (rest (cdr lis)))
365 (if (pair? rest)
366 (if (pred (car rest))
367 (lp rest (cdr rest))
368 (set-cdr! prev '()))))
369 lis)))
370
371 (define (span pred lis)
372 (let recur ((lis lis)
373 (in '()))
374 (if (null-list? lis)
375 (values (reverse! in) '())
376 (if (pred (car lis))
377 (recur (cdr lis) (cons (car lis) in))
378 (values (reverse! in) lis)))))
379
380 (define (span! pred lis)
381 (if (or (null-list? lis)
382 (not (pred (car lis))))
383 (values '() lis)
384 (let ((suffix (let lp ((prev lis) (rest (cdr lis)))
385 (if (null-list? rest) rest
386 (let ((x (car rest)))
387 (if (pred x)
388 (lp rest (cdr rest))
389 (begin (set-cdr! prev '())
390 rest)))))))
391 (values lis suffix))))
392
393 (define (break pred lis) (span (^x (not (pred x))) lis))
394 (define (break! pred lis) (span! (^x (not (pred x))) lis))
395
396 (define (list-index pred lis1 . lists)
397 (if (pair? lists)
398
399 ;; N-ary case
400 (let lp ((lists (cons lis1 lists)) (n 0))
401 (receive (heads tails) (%cars+cdrs lists)
402 (and (pair? heads)
403 (if (apply pred heads) n
404 (lp tails (+ n 1))))))
405
406 ;; Fast path
407 (let lp ((lis lis1) (n 0))
408 (and (not (null-list? lis))
409 (if (pred (car lis)) n (lp (cdr lis) (+ n 1)))))))
410
411 ;;;
412 ;;; Lists as sets of SRFI-1
413 ;;;
414
415 ;;; This is carefully tuned code; do not modify casually.
416 ;;; - It is careful to share storage when possible;
417 ;;; - Side-effecting code tries not to perform redundant writes.
418 ;;; - It tries to avoid linear-time scans in special cases where constant-time
419 ;;; computations can be performed.
420 ;;; - It relies on similar properties from the other list-lib procs it calls.
421 ;;; For example, it uses the fact that the implementations of MEMBER and
422 ;;; FILTER in this source code share longest common tails between args
423 ;;; and results to get structure sharing in the lset procedures.
424
425 (define (%lset2<= = lis1 lis2) (every (^x (member x lis2 =)) lis1))
426
427 (define (lset<= = . lists)
428 (check-arg procedure? =)
429 (or (not (pair? lists)) ; 0-ary case
430 (let lp ((s1 (car lists)) (rest (cdr lists)))
431 (or (not (pair? rest))
432 (let ((s2 (car rest)) (rest (cdr rest)))
433 (and (or (eq? s2 s1) ; Fast path
434 (%lset2<= = s1 s2)) ; Real test
435 (lp s2 rest)))))))
436
437 (define (lset= = . lists)
438 (check-arg procedure? =)
439 (or (not (pair? lists)) ; 0-ary case
440 (let lp ((s1 (car lists)) (rest (cdr lists)))
441 (or (not (pair? rest))
442 (let ((s2 (car rest))
443 (rest (cdr rest)))
444 (and (or (eq? s1 s2) ; Fast path
445 (and (%lset2<= = s1 s2)
446 (%lset2<= (^[y x] (= x y)) s2 s1))) ; Real test
447 (lp s2 rest)))))))
448
449
450 (define (lset-adjoin = lis . elts)
451 (check-arg procedure? =)
452 (fold (lambda (elt ans) (if (member elt ans =) ans (cons elt ans)))
453 lis elts))
454
455
456 (define (lset-union = . lists)
457 (check-arg procedure? =)
458 (reduce (lambda (lis ans) ; Compute ANS + LIS.
459 (cond ((null? lis) ans) ; Don't copy any lists
460 ((null? ans) lis) ; if we don't have to.
461 ((eq? lis ans) ans)
462 (else
463 (fold (lambda (elt ans) (if (any (^x (= x elt)) ans)
464 ans
465 (cons elt ans)))
466 ans lis))))
467 '() lists))
468
469 (define (lset-union! = . lists)
470 (check-arg procedure? =)
471 (reduce (lambda (lis ans) ; Splice new elts of LIS onto the front of ANS.
472 (cond ((null? lis) ans) ; Don't copy any lists
473 ((null? ans) lis) ; if we don't have to.
474 ((eq? lis ans) ans)
475 (else
476 (pair-fold (lambda (pair ans)
477 (let ((elt (car pair)))
478 (if (any (^x (= x elt)) ans)
479 ans
480 (begin (set-cdr! pair ans) pair))))
481 ans lis))))
482 '() lists))
483
484
485 (define (lset-intersection = lis1 . lists)
486 (check-arg procedure? =)
487 (let ((lists (delete lis1 lists eq?))) ; Throw out any LIS1 vals.
488 (cond ((any null-list? lists) '()) ; Short cut
489 ((null? lists) lis1) ; Short cut
490 (else (filter (lambda (x)
491 (every (lambda (lis) (member x lis =)) lists))
492 lis1)))))
493
494 (define (lset-intersection! = lis1 . lists)
495 (check-arg procedure? =)
496 (let ((lists (delete lis1 lists eq?))) ; Throw out any LIS1 vals.
497 (cond ((any null-list? lists) '()) ; Short cut
498 ((null? lists) lis1) ; Short cut
499 (else (filter! (lambda (x)
500 (every (lambda (lis) (member x lis =)) lists))
501 lis1)))))
502
503
504 (define (lset-difference = lis1 . lists)
505 (check-arg procedure? =)
506 (let ((lists (filter pair? lists))) ; Throw out empty lists.
507 (cond ((null? lists) lis1) ; Short cut
508 ((memq lis1 lists) '()) ; Short cut
509 (else (filter (lambda (x)
510 (every (lambda (lis) (not (member x lis =)))
511 lists))
512 lis1)))))
513
514 (define (lset-difference! = lis1 . lists)
515 (check-arg procedure? =)
516 (let ((lists (filter pair? lists))) ; Throw out empty lists.
517 (cond ((null? lists) lis1) ; Short cut
518 ((memq lis1 lists) '()) ; Short cut
519 (else (filter! (lambda (x)
520 (every (lambda (lis) (not (member x lis =)))
521 lists))
522 lis1)))))
523
524
525 (define (lset-xor = . lists)
526 (check-arg procedure? =)
527 (reduce (lambda (b a) ; Compute A xor B:
528 ;; Note that this code relies on the constant-time
529 ;; short-cuts provided by LSET-DIFF+INTERSECTION,
530 ;; LSET-DIFFERENCE & APPEND to provide constant-time short
531 ;; cuts for the cases A = (), B = (), and A eq? B. It takes
532 ;; a careful case analysis to see it, but it's carefully
533 ;; built in.
534
535 ;; Compute a-b and a^b, then compute b-(a^b) and
536 ;; cons it onto the front of a-b.
537 (receive (a-b a-int-b) (lset-diff+intersection = a b)
538 (cond ((null? a-b) (lset-difference = b a))
539 ((null? a-int-b) (append b a))
540 (else (fold (lambda (xb ans)
541 (if (member xb a-int-b =) ans (cons xb ans)))
542 a-b
543 b)))))
544 '() lists))
545
546
547 (define (lset-xor! = . lists)
548 (check-arg procedure? =)
549 (reduce (lambda (b a) ; Compute A xor B:
550 ;; Note that this code relies on the constant-time
551 ;; short-cuts provided by LSET-DIFF+INTERSECTION,
552 ;; LSET-DIFFERENCE & APPEND to provide constant-time short
553 ;; cuts for the cases A = (), B = (), and A eq? B. It takes
554 ;; a careful case analysis to see it, but it's carefully
555 ;; built in.
556
557 ;; Compute a-b and a^b, then compute b-(a^b) and
558 ;; cons it onto the front of a-b.
559 (receive (a-b a-int-b) (lset-diff+intersection! = a b)
560 (cond ((null? a-b) (lset-difference! = b a))
561 ((null? a-int-b) (append! b a))
562 (else (pair-fold (lambda (b-pair ans)
563 (if (member (car b-pair) a-int-b =) ans
564 (begin (set-cdr! b-pair ans) b-pair)))
565 a-b
566 b)))))
567 '() lists))
568
569
570 (define (lset-diff+intersection = lis1 . lists)
571 (check-arg procedure? =)
572 (cond ((every null-list? lists) (values lis1 '())) ; Short cut
573 ((memq lis1 lists) (values '() lis1)) ; Short cut
574 (else (partition (lambda (elt)
575 (not (any (lambda (lis) (member elt lis =))
576 lists)))
577 lis1))))
578
579 (define (lset-diff+intersection! = lis1 . lists)
580 (check-arg procedure? =)
581 (cond ((every null-list? lists) (values lis1 '())) ; Short cut
582 ((memq lis1 lists) (values '() lis1)) ; Short cut
583 (else (partition! (lambda (elt)
584 (not (any (lambda (lis) (member elt lis =))
585 lists)))
586 lis1))))
587
588 (define map-in-order map) ; Gauche's map is already in order
589
590 (define alist-cons acons)