Debian Codegraph @

src/liblist.scm

raw
1 ;;;
2 ;;; liblist.scm - builtin list procedures
3 ;;;
4 ;;; Copyright (c) 2000-2024 Shiro Kawai <[email protected]>
5 ;;;
6 ;;; Redistribution and use in source and binary forms, with or without
7 ;;; modification, are permitted provided that the following conditions
8 ;;; are met:
9 ;;;
10 ;;; 1. Redistributions of source code must retain the above copyright
11 ;;; notice, this list of conditions and the following disclaimer.
12 ;;;
13 ;;; 2. Redistributions in binary form must reproduce the above copyright
14 ;;; notice, this list of conditions and the following disclaimer in the
15 ;;; documentation and/or other materials provided with the distribution.
16 ;;;
17 ;;; 3. Neither the name of the authors nor the names of its contributors
18 ;;; may be used to endorse or promote products derived from this
19 ;;; software without specific prior written permission.
20 ;;;
21 ;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 ;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 ;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 ;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 ;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 ;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 ;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 ;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 ;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 ;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 ;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 ;;;
33
34 (select-module gauche.internal)
35
36 (inline-stub
37 (.include "gauche/priv/configP.h"
38 "gauche/vminsn.h"))
39
40 ;;
41 ;; R5RS Standard procs
42 ;;
43
44 (select-module scheme)
45 (define-cproc pair? (obj) ::<boolean> :fast-flonum :constant
46 (inliner PAIRP) SCM_PAIRP)
47 (define-cproc cons (obj1 obj2) ::<pair> (inliner CONS)
48 (return (SCM_PAIR (Scm_Cons obj1 obj2))))
49 (define-cproc car (obj::<pair>) :constant
50 (inliner CAR) (setter set-car!) SCM_CAR)
51 (define-cproc cdr (obj::<pair>) :constant
52 (inliner CDR) (setter set-cdr!) SCM_CDR)
53 (define-cproc set-car! (obj::<pair> value) ::<void>
54 (Scm_SetCar (SCM_OBJ obj) value))
55 (define-cproc set-cdr! (obj::<pair> value) ::<void>
56 (Scm_SetCdr (SCM_OBJ obj) value))
57
58 (inline-stub
59 "#define CXR_SETTER(PRE, pre, tail) \
60 ScmObj cell = Scm_C##tail##r(obj); \
61 if (!SCM_PAIRP(cell)) \
62 Scm_Error(\"can't set c\" #pre #tail \"r of %S\", obj); \
63 SCM_SET_C##PRE##R(cell, value);
64 "
65 )
66 (define-cproc caar (obj::<pair>) :fast-flonum :constant
67 (inliner CAAR) (setter (obj value) ::<void> (CXR_SETTER A a a))
68 (return (Scm_Caar (SCM_OBJ obj))))
69 (define-cproc cadr (obj::<pair>) :fast-flonum :constant
70 (inliner CADR) (setter (obj value) ::<void> (CXR_SETTER A a d))
71 (return (Scm_Cadr (SCM_OBJ obj))))
72 (define-cproc cdar (obj::<pair>) :fast-flonum :constant
73 (inliner CDAR) (setter (obj value) ::<void> (CXR_SETTER D d a))
74 (return (Scm_Cdar (SCM_OBJ obj))))
75 (define-cproc cddr (obj::<pair>) :fast-flonum :constant
76 (inliner CDDR) (setter (obj value) ::<void> (CXR_SETTER D d d))
77 (return (Scm_Cddr (SCM_OBJ obj))))
78
79 ;; NB: we avoid using getter-with-setter here, since
80 ;; - The current compiler doesn't take advantage of locked setters
81 ;; - Using getter-with-setter loses the inferred closure name
82 ;; But this may change in future, of course.
83 (select-module gauche)
84 (define-syntax %define-cxr
85 (syntax-rules ()
86 ((_ name a b)
87 (begin
88 (define-inline (name x) (a (b x)))
89 (define-in-module scheme name name)
90 (set! (setter name) (^[x v] (set! (a (b x)) v)))
91 ))))
92
93 (%define-cxr caaar car caar)
94 (%define-cxr caadr car cadr)
95 (%define-cxr cadar car cdar)
96 (%define-cxr caddr car cddr)
97 (%define-cxr cdaar cdr caar)
98 (%define-cxr cdadr cdr cadr)
99 (%define-cxr cddar cdr cdar)
100 (%define-cxr cdddr cdr cddr)
101 (%define-cxr caaaar caar caar)
102 (%define-cxr caaadr caar cadr)
103 (%define-cxr caadar caar cdar)
104 (%define-cxr caaddr caar cddr)
105 (%define-cxr cadaar cadr caar)
106 (%define-cxr cadadr cadr cadr)
107 (%define-cxr caddar cadr cdar)
108 (%define-cxr cadddr cadr cddr)
109 (%define-cxr cdaaar cdar caar)
110 (%define-cxr cdaadr cdar cadr)
111 (%define-cxr cdadar cdar cdar)
112 (%define-cxr cdaddr cdar cddr)
113 (%define-cxr cddaar cddr caar)
114 (%define-cxr cddadr cddr cadr)
115 (%define-cxr cdddar cddr cdar)
116 (%define-cxr cddddr cddr cddr)
117
118 ;; primitives for immutable pars
119 (define-cproc ipair? (obj) ::<boolean> Scm_ImmutablePairP)
120 (define-cproc ipair (car cdr) ::<pair>
121 (return (SCM_PAIR (Scm_MakeImmutablePair car cdr SCM_NIL))))
122 (define-cproc ilist (:rest args) ::<list>
123 (if (SCM_NULLP args)
124 (return SCM_NIL)
125 (let* ([h SCM_NIL] [t SCM_NIL])
126 (dopairs (cp args)
127 (if (SCM_NULLP t)
128 (set! h (Scm_MakeImmutablePair (SCM_CAR cp) SCM_NIL SCM_NIL)
129 t h)
130 (let* ([p (Scm_MakeImmutablePair (SCM_CAR cp) SCM_NIL SCM_NIL)])
131 (SCM_SET_CDR_UNCHECKED t p)
132 (set! t p))))
133 (return h))))
134
135 (select-module scheme)
136 (define-cproc null? (obj) ::<boolean> :fast-flonum :constant
137 (inliner NULLP) SCM_NULLP)
138 (define-cproc list? (obj) ::<boolean> :fast-flonum :constant
139 SCM_PROPER_LIST_P)
140 (define-cproc list (:rest args) ::<list> (inliner LIST) (return args))
141
142 (define-cproc length (list) ::<long> :constant (inliner LENGTH)
143 (let* ([len::long (Scm_Length list)])
144 (when (< len 0) (Scm_Error "bad list: %S" list))
145 (return len)))
146
147 (select-module gauche)
148 (define-cproc length<=? (list k::<integer>) ::<boolean> :constant
149 (if (SCM_INTP k)
150 (let* ([n::ScmSmallInt (SCM_INT_VALUE k)])
151 (dolist [_ list] (when (<= (post-- n) 0) (return FALSE)))
152 (return (<= 0 n)))
153 ;; k is bignum. it is impossible to have that long list, but list
154 ;; can be circular, so we need to scan list entirely anyway.
155 (if (< (Scm_Sign k) 0)
156 (return FALSE)
157 (let* ([ln::ScmSmallInt (Scm_Length list)])
158 (return (>= ln 0))))))
159 (define-cproc length=? (list k::<integer>) ::<boolean> :constant
160 (if (SCM_INTP k)
161 (let* ([n::ScmSmallInt (SCM_INT_VALUE k)])
162 (dolist [_ list] (when (<= (post-- n) 0) (return FALSE)))
163 (return (== 0 n)))
164 (return FALSE)))
165 (define (length<? list k) (length<=? list (- k 1)))
166 (define (length>? list k) (not (length<=? list k)))
167 (define (length>=? list k) (not (length<? list k)))
168
169 (select-module scheme)
170 (define-cproc append (:rest lists) (inliner APPEND) Scm_Append)
171 (define-cproc reverse (list::<list> :optional (tail ())) Scm_Reverse2)
172
173 (define-cproc list-tail (list k::<fixnum> :optional fallback) :constant
174 Scm_ListTail)
175
176 ;; list-set! requires the first argument to be a <pair>, for
177 ;; passing length 0 list (proper or dotted) to list-set! is useless anyways.
178 ;; list-ref, on the other hand, can accept non-list argument (which is
179 ;; technically a dotted list of length 0), as far as FALLBACK is given.
180 ;; Cf. https://github.com/shirok/Gauche/issues/814
181
182 ;;We need to define list-set! as cproc in order to use it in the setter clause
183 ;;of list-ref. This limitation of cgen.stub should be removed in future.
184 ;;(define (list-set! lis k v) (set-car! (list-tail lis k) v))
185 (define-cproc list-set! (lis::<pair> k::<fixnum> v) ::<void>
186 (let* ([p (Scm_ListTail (SCM_OBJ lis) k SCM_FALSE)])
187 (if (SCM_PAIRP p)
188 (Scm_SetCar p v)
189 (Scm_Error "list-set!: index out of bound: %d" k))))
190 (define-cproc list-ref (lis k::<fixnum> :optional fallback) :constant
191 (setter list-set!)
192 ;; Better error message for the common mistake
193 (when (and (SCM_UNBOUNDP fallback) (not (SCM_LISTP lis)))
194 (Scm_Error "list-ref: argument must be a list, but got: %S" lis))
195 (return (Scm_ListRef (SCM_OBJ lis) k fallback)))
196
197 (define-cproc memq (obj list::<list>) :constant (inliner MEMQ) Scm_Memq)
198 (define-cproc memv (obj list::<list>) :constant (inliner MEMV) Scm_Memv)
199
200 (define-cproc assq (obj alist::<list>) :constant (inliner ASSQ) Scm_Assq)
201 (define-cproc assv (obj alist::<list>) :constant (inliner ASSV) Scm_Assv)
202
203 (select-module gauche.internal)
204 ;; Actual member and assoc is defined blow.
205 (define-cproc %member (obj list::<list>)
206 (return (Scm_Member obj list SCM_CMP_EQUAL)))
207 (define-cproc %assoc (obj alist::<list>)
208 (return (Scm_Assoc obj alist SCM_CMP_EQUAL)))
209
210 ;;
211 ;; Some extra procedures
212 ;;
213
214 (select-module gauche)
215 (define-cproc length+ (list) ::<integer>? :constant ;; SRFI-1
216 (let* ([i::int (Scm_Length list)])
217 (if (< i 0) (return SCM_FALSE) (return (Scm_MakeInteger i)))))
218
219 ;; Like length, but works on dotted and circular lists.
220 ;; To avoid overhead for typical cases, we first use hare and tortoise to
221 ;; detect circle, and only use hashtable to count pairs after we determine
222 ;; list is circular.
223 (define (num-pairs list)
224 (define (count-pairs-in-circle)
225 (let1 tab (make-hash-table 'eq?)
226 (let loop ([list list])
227 (if (hash-table-exists? tab list)
228 (hash-table-num-entries tab)
229 (begin (hash-table-put! tab list #t)
230 (loop (cdr list)))))))
231 (let loop ([n 0] [slow list] [list list])
232 (if (pair? list)
233 (if (pair? (cdr list))
234 (if (eq? slow (cdr list))
235 (count-pairs-in-circle)
236 (loop (+ n 2) (cdr slow) (cddr list)))
237 (+ n 1))
238 n)))
239
240 (define-cproc proper-list? (obj) ::<boolean> :constant SCM_PROPER_LIST_P)
241 (define-cproc dotted-list? (obj) ::<boolean> :constant SCM_DOTTED_LIST_P)
242 (define-cproc circular-list? (obj) ::<boolean> :constant SCM_CIRCULAR_LIST_P)
243 (define-cproc make-list (len::<fixnum> :optional (fill #f)) Scm_MakeList)
244 (define-cproc acons (caa cda cd) ::<pair>
245 (return (SCM_PAIR (Scm_Acons caa cda cd))))
246 (define-cproc last-pair (list) :constant Scm_LastPair)
247 (define-cproc list-copy (list) Scm_CopyList)
248
249 (define-cproc list* (arg :rest args)
250 (inliner LIST-STAR)
251 (if (SCM_NULLP args)
252 (return arg)
253 (let* ([head (SCM_LIST1 arg)] [tail head])
254 (dopairs [cp args]
255 (unless (SCM_PAIRP (SCM_CDR cp))
256 (SCM_SET_CDR_UNCHECKED tail (SCM_CAR cp))
257 (break))
258 (SCM_APPEND1 head tail (SCM_CAR cp)))
259 (return head))))
260
261 (define-cproc append! (:rest list)
262 (let* ([h '()] [t '()])
263 (dopairs [cp list]
264 (when (SCM_NULLP (SCM_CDR cp))
265 (if (SCM_NULLP h)
266 (set! h (SCM_CAR cp))
267 (Scm_SetCdr t (SCM_CAR cp)))
268 (break))
269 (SCM_APPEND h t (SCM_CAR cp))
270 (unless (or (SCM_NULLP t) (SCM_NULLP (SCM_CDR t)))
271 (Scm_Error "proper list required, but got %S" (SCM_CAR cp))))
272 (return h)))
273
274 (define-cproc reverse! (list :optional (tail ())) Scm_Reverse2X)
275
276 (define-cproc monotonic-merge (sequences::<list>) ::<list> Scm_MonotonicMerge1)
277
278 (select-module gauche.internal)
279 (define-in-module scheme (map proc lis . more)
280 (if (null? more)
281 (let loop ([xs lis] [r '()])
282 (cond [(pair? xs) (loop (cdr xs) (cons (proc (car xs)) r))]
283 [(null? xs) (reverse r)]
284 [else (error "improper list not allowed:" lis)]))
285 (let loop ([xss (cons lis more)] [r '()])
286 (receive (cars cdrs) (%zip-nary-args xss)
287 (if (not cars)
288 (reverse r)
289 (loop cdrs (cons (apply proc cars) r)))))))
290
291 (define-in-module scheme (for-each proc lis . more)
292 (if (null? more)
293 (let loop ([xs lis])
294 (cond [(pair? xs) (proc (car xs)) (loop (cdr xs))]
295 [(null? xs) (undefined)]
296 [else (error "improper list not allowed:" lis)]))
297 (let loop ([xss (cons lis more)])
298 (receive (cars cdrs) (%zip-nary-args xss)
299 (unless (not cars)
300 (apply proc cars)
301 (loop cdrs))))))
302
303 (select-module gauche)
304 (define-inline (null-list? l) ;SRFI-1
305 (cond [(null? l)]
306 [(pair? l) #f]
307 [else (error "argument must be a list, but got:" l)]))
308
309 (define-inline cons* list*) ;SRFI-1
310
311 (define (last lis) (car (last-pair lis))) ;SRFI-1
312
313 (define (iota count :optional (start 0) (step 1)) ;SRFI-1
314 (unless (and (integer? count) (>= count 0))
315 (error "count must be nonnegative integer: " count))
316 (if (and (exact? start) (exact? step))
317 ;; we allow inexact integer as 'count', for the consistency of
318 ;; giota and liota in which we can also accept +inf.0 as count.
319 (let1 count (exact count)
320 (do ([c count (- c 1)]
321 [v (+ start (* (- count 1) step)) (- v step)]
322 [r '() (cons v r)])
323 [(<= c 0) r]))
324 ;; for inexact numbers, we use multiplication to avoid error accumulation.
325 (do ([c count (- c 1)]
326 [r '() (cons (+ start (*. (- c 1) step)) r)])
327 [(<= c 0) r])))
328
329 (select-module gauche.internal)
330 (inline-stub
331 ;; translate cmpmode argument
332 (define-cfn getcmpmode (opt) ::int :static
333 (cond
334 [(or (SCM_UNBOUNDP opt) (SCM_EQ opt 'equal?)) (return SCM_CMP_EQUAL)]
335 [(SCM_EQ opt 'eq?) (return SCM_CMP_EQ)]
336 [(SCM_EQ opt 'eqv?) (return SCM_CMP_EQV)]
337 [else (Scm_Error "unrecognized compare mode: %S" opt) (return 0)]))
338 )
339
340 (define-cproc %delete (obj list::<list> :optional cmpmode)
341 (return (Scm_Delete obj list (getcmpmode cmpmode))))
342 (define-cproc %delete! (obj list::<list> :optional cmpmode)
343 (return (Scm_DeleteX obj list (getcmpmode cmpmode))))
344 (define-cproc %delete-duplicates (list::<list> :optional cmpmode)
345 (return (Scm_DeleteDuplicates list (getcmpmode cmpmode))))
346 (define-cproc %delete-duplicates! (list::<list> :optional cmpmode)
347 (return (Scm_DeleteDuplicatesX list (getcmpmode cmpmode))))
348 (define-cproc %alist-delete (elt list::<list> :optional cmpmode)
349 (return (Scm_AssocDelete elt list (getcmpmode cmpmode))))
350 (define-cproc %alist-delete! (elt list::<list> :optional cmpmode)
351 (return (Scm_AssocDeleteX elt list (getcmpmode cmpmode))))
352
353 (define-in-module gauche.internal (%zip-nary-args arglists . seed)
354 (let loop ([as arglists]
355 [cars '()]
356 [cdrs '()])
357 (cond [(null? as)
358 (values (reverse! (if (null? seed) cars (cons (car seed) cars)))
359 (reverse! cdrs))]
360 [(null? (car as)) (values #f #f)] ;;exhausted
361 [(pair? (car as))
362 (loop (cdr as) (cons (caar as) cars) (cons (cdar as) cdrs))]
363 [else
364 (error "argument lists contained an improper list ending with:"
365 (car as))])))
366
367 ;; In the common case, these procs uses Gauche native, even not loading
368 ;; the generic filter routine.
369 (define-syntax %case-by-cmp
370 (syntax-rules ()
371 [(_ args = eq-case eqv-case equal-case default-case)
372 (let1 = (if (pair? args) (car args) equal?)
373 (cond [(eq? = eq?) eq-case]
374 [(eq? = eqv?) eqv-case]
375 [(eq? = equal?) equal-case]
376 [else default-case]))]))
377
378 (define-in-module gauche (delete x lis . args)
379 (%case-by-cmp args =
380 (%delete x lis 'eq?)
381 (%delete x lis 'eqv?)
382 (%delete x lis 'equal?)
383 (filter (^y (not (= x y))) lis)))
384
385 (define-in-module gauche (delete! x lis . args)
386 (%case-by-cmp args =
387 (%delete! x lis 'eq?)
388 (%delete! x lis 'eqv?)
389 (%delete! x lis 'equal?)
390 (filter! (^y (not (= x y))) lis)))
391
392 (define-in-module scheme (member x lis . args)
393 (%case-by-cmp args =
394 (memq x lis)
395 (memv x lis)
396 (%member x lis)
397 (find-tail (^y (= x y)) lis)))
398
399 (define-in-module gauche (delete-duplicates lis . args)
400 (%case-by-cmp args =
401 (%delete-duplicates lis 'eq?)
402 (%delete-duplicates lis 'eqv?)
403 (%delete-duplicates lis 'equal?)
404 (let recur ([lis lis])
405 (if (null-list? lis) lis
406 (let* ([x (car lis)]
407 [tail (cdr lis)]
408 [new-tail (recur (delete x tail =))])
409 (if (eq? tail new-tail) lis (cons x new-tail)))))))
410
411 (define-in-module gauche (delete-duplicates! lis . args)
412 (%case-by-cmp args =
413 (%delete-duplicates! lis 'eq?)
414 (%delete-duplicates! lis 'eqv?)
415 (%delete-duplicates! lis 'equal?)
416 (let recur ((lis lis))
417 (if (null-list? lis) lis
418 (let* ((x (car lis))
419 (tail (cdr lis))
420 (new-tail (recur (delete! x tail =))))
421 (if (eq? tail new-tail) lis (cons x new-tail)))))))
422
423 ;;
424 ;; Higher-order stuff
425 ;;
426
427 (select-module gauche)
428
429 (define (any pred lis . more)
430 (if (null? more)
431 (and (not (null-list? lis))
432 (let loop ((head (car lis)) (tail (cdr lis)))
433 (cond [(null-list? tail) (pred head)] ; tail call
434 [(pred head)]
435 [else (loop (car tail) (cdr tail))])))
436 (let loop ([liss (cons lis more)])
437 (receive (cars cdrs) ((with-module gauche.internal %zip-nary-args) liss)
438 (cond [(not cars) #f]
439 [(apply pred cars)]
440 [else (loop cdrs)])))))
441
442 (define (every pred lis . more)
443 (if (null? more)
444 (or (null-list? lis)
445 (let loop ([head (car lis)] [tail (cdr lis)])
446 (cond [(null-list? tail) (pred head)] ; tail call
447 [(not (pred head)) #f]
448 [else (loop (car tail) (cdr tail))])))
449 (receive (heads tails)
450 ((with-module gauche.internal %zip-nary-args) (cons lis more))
451 (or (not heads)
452 (let loop ([heads heads] [tails tails])
453 (receive (next-heads next-tails)
454 ((with-module gauche.internal %zip-nary-args) tails)
455 (if next-heads
456 (and (apply pred heads)
457 (loop next-heads next-tails))
458 (apply pred heads))))))))
459
460 (define (filter pred lis)
461 (let loop ([lis lis] [r '()])
462 (cond [(null-list? lis) (reverse r)]
463 [(pred (car lis)) (loop (cdr lis) (cons (car lis) r))]
464 [else (loop (cdr lis) r)])))
465
466 (define (filter! pred lis)
467 (define (keep! prev lis)
468 (when (pair? lis)
469 (if (pred (car lis))
470 (keep! lis (cdr lis))
471 (skip! prev (cdr lis)))))
472 (define (skip! prev lis)
473 (let loop ([lis lis])
474 (cond [(not (pair? lis)) (set-cdr! prev lis)]
475 [(pred (car lis)) (set-cdr! prev lis) (keep! lis (cdr lis))]
476 [else (loop (cdr lis))])))
477 (let restart ([ans lis])
478 (cond [(null-list? ans) ans]
479 [(not (pred (car ans))) (restart (cdr ans))]
480 [else (keep! ans (cdr ans)) ans])))
481
482 (define (remove pred l) (filter (^x (not (pred x))) l))
483 (define (remove! pred l) (filter! (^x (not (pred x))) l))
484
485 (define (filter-map fn lis . more)
486 (if (null? more)
487 (let loop ([lis lis] [r '()])
488 (cond [(null-list? lis) (reverse r)]
489 [(fn (car lis)) => (^x (loop (cdr lis) (cons x r)))]
490 [else (loop (cdr lis) r)]))
491 (let loop ([liss (cons lis more)] [r '()])
492 (receive (cars cdrs)
493 ((with-module gauche.internal %zip-nary-args) liss)
494 (cond [(not cars) (reverse r)]
495 [(apply fn cars) => (^x (loop cdrs (cons x r)))]
496 [else (loop cdrs r)])))))
497
498 (define (fold kons knil lis . more)
499 (if (null? more)
500 (let loop ([lis lis] [knil knil])
501 (if (null-list? lis) knil (loop (cdr lis) (kons (car lis) knil))))
502 (let loop ([liss (cons lis more)] [knil knil])
503 (receive (cars cdrs)
504 ((with-module gauche.internal %zip-nary-args) liss knil)
505 (if cars
506 (loop cdrs (apply kons cars))
507 knil)))))
508
509 (define (fold-left snok knil lis . more)
510 (if (null? more)
511 (let loop ([lis lis] [knil knil])
512 (if (null-list? lis) knil (loop (cdr lis) (snok knil (car lis)))))
513 (let loop ([liss (cons lis more)] [knil knil])
514 (receive (cars- cdrs)
515 ((with-module gauche.internal %zip-nary-args) liss)
516 (if cars-
517 (loop cdrs (apply snok knil cars-))
518 knil)))))
519
520 (define (fold-right kons knil lis . more)
521 (if (null? more)
522 (let rec ([lis lis])
523 (if (null-list? lis)
524 knil
525 (kons (car lis) (rec (cdr lis)))))
526 (let rec ([liss (cons lis more)])
527 (receive (cars cdrs) ((with-module gauche.internal %zip-nary-args) liss)
528 (if cars
529 (apply kons (append! cars (list (rec cdrs))))
530 knil)))))
531
532 (define (count pred lis . more)
533 (if (null? more)
534 (let rec ([lis lis] [cnt 0])
535 (if (null-list? lis)
536 cnt
537 (rec (cdr lis) (if (pred (car lis)) (+ cnt 1) cnt))))
538 (let rec ([liss (cons lis more)] [cnt 0])
539 (receive (cars cdrs) ((with-module gauche.internal %zip-nary-args) liss)
540 (if cars
541 (rec cdrs (if (apply pred cars) (+ cnt 1) cnt))
542 cnt)))))
543
544 (define (reduce f ridentity lis)
545 (if (null-list? lis)
546 ridentity
547 (fold f (car lis) (cdr lis))))
548
549 (define (reduce-right f ridentity lis)
550 (if (null-list? lis)
551 ridentity
552 (let rec ([head (car lis)] [lis (cdr lis)])
553 (if (pair? lis)
554 (f head (rec (car lis) (cdr lis)))
555 head))))
556
557 (define (append-reverse list tail) (reverse list tail)) ;SRFI-1 compat
558 (define (append-reverse! list tail) (reverse! list tail));SRFI-1 compat
559
560 (define (concatenate lists) (reduce-right append '() lists))
561 (define (concatenate! lists) (reduce-right append! '() lists))
562
563 (define (append-map f lis . lists) (concatenate (apply map f lis lists)))
564 (define (append-map! f lis . lists) (concatenate! (apply map f lis lists)))
565
566 (define (map* fn tail-fn lis . more)
567 (if (null? more)
568 (let rec ([xs lis] [rs '()])
569 (if (pair? xs)
570 (rec (cdr xs) (cons (fn (car xs)) rs))
571 (reverse rs (tail-fn xs))))
572 (let rec ([xss (cons lis more)] [rs '()])
573 (if (every pair? xss)
574 (receive (cars cdrs) ((with-module gauche.internal %zip-nary-args) xss)
575 (rec cdrs (cons (apply fn cars) rs)))
576 (reverse rs (apply tail-fn xss))))))
577
578 (define (find pred lis)
579 (let loop ([lis lis])
580 (cond [(not (pair? lis)) #f]
581 [(pred (car lis)) (car lis)]
582 [else (loop (cdr lis))])))
583
584 (define (find-tail pred lis)
585 (let loop ([lis lis])
586 (cond [(not (pair? lis)) #f]
587 [(pred (car lis)) lis]
588 [else (loop (cdr lis))])))
589
590 (define (split-at lis i)
591 (let loop ([i i] [rest lis] [r '()])
592 (cond [(= i 0) (values (reverse! r) rest)]
593 [(null? rest) (error "given list is too short:" lis)]
594 [else (loop (- i 1) (cdr rest) (cons (car rest) r))])))
595
596 (define (split-at! lis i)
597 (let loop ([i i] [rest lis] [prev #f])
598 (cond [(= i 0) (if prev
599 (begin (set-cdr! prev '()) (values lis rest))
600 (values '() rest))]
601 [(null? rest) (error "given list is too short:" lis)]
602 [else (loop (- i 1) (cdr rest) rest)])))
603
604 ;; partition is here, for gauche.procedure has partition$ and we don't
605 ;; want it to depend on SRFI-1. partition! is left in SRFI-1, for its
606 ;; optimized version is rather complicated.
607 (define (partition pred lis)
608 (let rec ([lis lis] [xs '()] [ys '()])
609 (if (null-list? lis)
610 (values (reverse! xs) (reverse! ys))
611 (if (pred (car lis))
612 (rec (cdr lis) (cons (car lis) xs) ys)
613 (rec (cdr lis) xs (cons (car lis) ys))))))
614
615 (define (take list k)
616 (let loop ([lis list] [r '()] [j k])
617 (cond [(= j 0) (reverse! r)]
618 [(pair? lis) (loop (cdr lis) (cons (car lis) r) (- j 1))]
619 [else (errorf "take: input list is too short (expected at least \
620 ~a elements, but only ~a elements long): ~,,,,70s"
621 k (- k j) list)])))
622
623 (define drop list-tail) ; SRFI-1
624
625 (define (take-right lis k)
626 (let loop ([p0 (list-tail lis k)] [p1 lis])
627 (if (pair? p0) (loop (cdr p0) (cdr p1)) p1)))
628
629 (define (drop-right lis k)
630 (let rec ([p0 (list-tail lis k)] [p1 lis])
631 (if (pair? p0) (cons (car p1) (rec (cdr p0) (cdr p1))) '())))
632
633 (define (take! lis k)
634 (cond [(zero? k) '()]
635 [else (set-cdr! (list-tail lis (- k 1)) '()) lis]))
636
637 (define (drop-right! lis k)
638 (let1 p0 (list-tail lis k)
639 (if (pair? p0)
640 (let loop ([p0 (cdr p0)] [p1 lis])
641 (if (pair? p0)
642 (loop (cdr p0) (cdr p1))
643 (begin (set-cdr! p1 '()) lis)))
644 '())))
645
646 ;; Permissive versions
647 (define (split-at* lis k :optional (fill? #f) (filler #f))
648 (when (or (not (integer? k)) (negative? k))
649 (error "index must be non-negative integer" k))
650 (let loop ((i 0)
651 (lis lis)
652 (r '()))
653 (cond [(= i k) (values (reverse! r) lis)]
654 [(null? lis)
655 (values (if fill?
656 (append! (reverse! r) (make-list (- k i) filler))
657 (reverse! r))
658 lis)]
659 [else (loop (+ i 1) (cdr lis) (cons (car lis) r))])))
660
661 (define (take* lis k . args)
662 (receive (h t) (apply split-at* lis k args) h))
663
664 (define (drop* lis k)
665 (when (or (not (integer? k)) (negative? k))
666 (error "index must be non-negative integer" k))
667 (let loop ((i 0)
668 (lis lis))
669 (cond [(= i k) lis]
670 [(null? lis) '()]
671 [else (loop (+ i 1) (cdr lis))])))
672
673 (with-module gauche.internal
674 ;; A tolerant version of list-tail. If LIS is shorter than K, returns
675 ;; (- k (length lis)) as the second value.
676 (define (%list-tail* lis k)
677 (let loop ([lis lis] [k k])
678 (cond [(<= k 0) (values lis 0)]
679 [(null? lis) (values lis k)]
680 [else (loop (cdr lis) (- k 1))])))
681 )
682
683 (define (take-right* lis k :optional (fill? #f) (filler #f))
684 (when (or (not (integer? k)) (negative? k) (inexact? k))
685 (error "index must be non-negative exact integer" k))
686 ;; NB: This procedure can be used to take the last K elements of
687 ;; a huge lazy list. (Not so much in take-right, with which you need
688 ;; to know the length of list is greater than K beforehand.)
689 ;; The naive implementation (drop lis (- (length lis) k)) would require
690 ;; to realize entire list on memory, which we want to avoid.
691 ;; We overwrite LIS and TAIL in each iteration instead of rebinding it,
692 ;; in order to release reference to the head of list.
693 (receive (tail j) ((with-module gauche.internal %list-tail*) lis k)
694 (if (= j 0)
695 (let loop ()
696 (if (pair? tail)
697 (begin (set! lis (cdr lis))
698 (set! tail (cdr tail))
699 (loop))
700 lis))
701 (if fill?
702 (append! (make-list j filler) lis)
703 lis))))
704
705 (define (drop-right* lis k)
706 (let1 len (length lis)
707 (if (<= k len) (take lis (- len k)) '())))
708
709 ;; slices - split a list to a bunch of sublists of length k
710 (define (slices lis k . args)
711 (unless (and (integer? k) (positive? k))
712 (error "index must be positive integer" k))
713 (let loop ([lis lis]
714 [r '()])
715 (if (null? lis)
716 (reverse! r)
717 (receive (h t) (apply split-at* lis k args)
718 (loop t (cons h r))))))
719
720 ;; intersperse - insert ITEM between elements in the list.
721 ;; (the order of arguments is taken from Haskell's intersperse)
722 (define (intersperse item lis)
723 (define (rec l r)
724 (if (null? l)
725 (reverse! r)
726 (rec (cdr l) (list* (car l) item r))))
727 (if (null? lis)
728 '()
729 (rec (cdr lis) (list (car lis)))))
730
731 ;;
732 ;; Assoc lists
733 ;;
734
735 (select-module gauche)
736 (define-cproc alist-copy (alist) Scm_AlistCopy)
737
738 (select-module gauche.internal)
739 (define-in-module scheme (assoc x lis . args)
740 (%case-by-cmp args =
741 (assq x lis)
742 (assv x lis)
743 (%assoc x lis)
744 (find (^[entry] (= x (car entry))) lis)))
745
746 (define-in-module gauche (alist-delete key alist . args)
747 (%case-by-cmp args =
748 (%alist-delete key alist 'eq?)
749 (%alist-delete key alist 'eqv?)
750 (%alist-delete key alist 'equal?)
751 (filter (^[elt] (not (= key (car elt)))) alist)))
752
753 (define-in-module gauche (alist-delete! key alist . args)
754 (%case-by-cmp args =
755 (%alist-delete! key alist 'eq?)
756 (%alist-delete! key alist 'eqv?)
757 (%alist-delete! key alist 'equal?)
758 (filter! (^[elt] (not (= key (car elt)))) alist)))
759
760 (select-module gauche)
761 ;; `reverse' alist search fn
762 (define (rassoc key alist :optional (eq equal?))
763 (find (^[elt] (and (pair? elt) (eq (cdr elt) key))) alist))
764
765 (define rassq (cut rassoc <> <> eq?))
766 (define rassv (cut rassoc <> <> eqv?))
767
768 (define (alist-ref alist key :optional (eq equal?) (default #f))
769 (cond [(assoc key alist eq) => cdr]
770 [else default]))
771 (define (alist-key alist val :optional (eq equal?) (default #f))
772 (cond [(rassoc val alist eq) => car]
773 [else default]))
774 (define (alist-set! alist key val :optional (eq equal?))
775 (cond [(assoc key alist eq) => (^p (set-cdr! p val) alist)]
776 [else (acons key val alist)]))
777
778 (define (alist-adjoin alist key val :optional (eq equal?))
779 (define (rec alis)
780 (cond [(null? alis) '()]
781 [(eq key (caar alis)) (acons key val (cdr alis))]
782 [else (let1 tail (rec (cdr alis))
783 (if (eq? tail (cdr alis))
784 alis
785 (cons (car alis) tail)))]))
786 (let1 r (rec alist)
787 (if (eq? r alist)
788 (acons key val alist)
789 r)))
790
791 (define (alist-merge maybe-eq reducer . args)
792 (define (merge* eq reducer alists)
793 (cond [(null? alists) '()]
794 [(null? (cdr alists)) (car alists)]
795 [(null? (cddr alists))
796 (merge2 eq reducer '() (car alists) (cadr alists))]
797 [else
798 (merge2 eq reducer '() (car alists)
799 (merge* eq reducer (cdr alists)))]))
800 (define (merge2 eq reducer visited-keys alist1 alist2)
801 (if (null? alist1)
802 (remove (^p (member (car p) visited-keys)) alist2)
803 (let* ([key (caar alist1)]
804 [found (assoc key alist2 eq)])
805 (if found
806 (acons key (reducer (cdar alist1) (cdr found))
807 (merge2 eq reducer (cons key visited-keys)
808 (cdr alist1) alist2))
809 (cons (car alist1)
810 (merge2 eq reducer visited-keys (cdr alist1) alist2))))))
811 (if (list? reducer) ;eq proc is omitted
812 (merge* equal? maybe-eq (cons reducer args))
813 (merge* maybe-eq reducer args)))
814
815 (define (alist-update-in alist keys proc :optional (key= equal?) (default #f))
816 (define (rec alist key keys)
817 (if (null? keys)
818 (let1 val (assoc-ref alist key default key=)
819 (assoc-adjoin alist key (proc val) key=))
820 (let1 val (assoc-ref alist key '() key=)
821 (assoc-adjoin alist key (rec val (car keys) (cdr keys)) key=))))
822 (if (null? keys)
823 (error "needs at least one key in assoc-update")
824 (rec alist (car keys) (cdr keys))))
825
826 ;; for backward compatibity
827 (define (assoc-ref alist key :optional (default #f) (eq-fn equal?))
828 (alist-ref alist key eq-fn default))
829 (define (assq-ref alist key :optional (default #f))
830 (alist-ref alist key eq? default))
831 (define (assv-ref alist key :optional (default #f))
832 (alist-ref alist key eqv? default))
833 (define (rassoc-ref alist val :optional (default #f) (eq-fn equal?))
834 (alist-key alist val eq-fn default))
835 (define (rassq-ref alist val :optional (default #f))
836 (alist-key alist val eq? default))
837 (define (rassv-ref alist val :optional (default #f))
838 (alist-key alist val eqv? default))
839 (define assoc-set! alist-set!)
840 (define assq-set! (cut alist-set! <> <> <> eq?))
841 (define assv-set! (cut alist-set! <> <> <> eqv?))
842 (define assoc-adjoin alist-adjoin)
843 (define (assoc-update-in alist keys proc :optional (default #f) (eq-fn equal?))
844 (alist-update-in alist keys proc eq-fn default))
845
846 ;;;
847 ;;; Extended pairs
848 ;;;
849
850 (select-module gauche)
851
852 (define-cproc extended-pair? (obj) ::<boolean> SCM_EXTENDED_PAIR_P)
853 (define-cproc extended-cons (car cdr :optional (attrs ()))
854 (let* ([z (Scm_ExtendedCons car cdr)])
855 (unless (SCM_NULLP attrs)
856 (for-each (lambda (p)
857 (unless (SCM_PAIRP p)
858 (Scm_Error "Assoc list required, but got: %S" attrs))
859 (Scm_PairAttrSet (SCM_PAIR z) (SCM_CAR p) (SCM_CDR p)))
860 (Scm_Reverse attrs)))
861 (return z)))
862 (define-cproc extended-list (elt :rest more) ::<list> Scm_ExtendedCons)
863
864 (define-cproc pair-attributes (pair::<pair>) Scm_PairAttr)
865
866 (define-cproc pair-attribute-get (pair::<pair> key :optional fallback)
867 (return (Scm_PairAttrGet (SCM_PAIR pair) key fallback)))
868
869 (define-cproc pair-attribute-set! (pair::<pair> key value)
870 (return (Scm_PairAttrSet (SCM_PAIR pair) key value)))