| 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) |