Debian Codegraph @

lib/scheme/ilist.scm

raw
1 ;;;
2 ;;; scheme.ilist - immutable lists (R7RS Red)
3 ;;;
4 ;;; Copyright (c) 2017-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 ;; Originally SRFI-116
35
36 ;; Gauche supports immutable pairs natively. They work transparently
37 ;; as mutable pairs, except set-car! and set-cdr!.
38 ;; Procedures that don't cons are just alias of builtin procedures.
39 ;; Whenever a procedure need to cons, we make an ipair instead of an mpair.
40
41 ;; Note that we won't reject mpair passed to these procedures.
42
43 (define-module scheme.ilist
44 (use scheme.list)
45 (use srfi.114 :only (make-car-comparator
46 make-cdr-comparator
47 make-pair-comparator
48 make-improper-list-comparator))
49 (use util.match)
50 (export ipair ;builtin
51 ilist ;builtin
52 xipair ipair* make-ilist ilist-tabulate
53 ilist-copy iiota
54
55 iq
56
57 ipair? ;builtin
58 ;; NB: Other predicates don't distinguish mutable and immutable
59 ;; pairs.
60 (rename proper-list? proper-ilist?)
61 (rename list? ilist?)
62 (rename dotted-list? dotted-ilist?)
63 (rename not-pair? not-ipair?)
64 (rename null-list? null-ilist?)
65 (rename list= ilist=)
66
67 (rename car icar) (rename cdr icdr)
68 (rename caar icaar) (rename cadr icadr)
69 (rename cdar icdar) (rename cddr icddr)
70 (rename caaar icaaar) (rename caadr icaadr)
71 (rename cadar icadar) (rename caddr icaddr)
72 (rename cdaar icdaar) (rename cdadr icdadr)
73 (rename cddar icddar) (rename cdddr icdddr)
74 (rename caaaar icaaaar) (rename caaadr icaaadr)
75 (rename caadar icaadar) (rename caaddr icaaddr)
76 (rename cadaar icadaar) (rename cadadr icadadr)
77 (rename caddar icaddar) (rename cadddr icadddr)
78 (rename cdaaar icdaaar) (rename cdaadr icdaadr)
79 (rename cdadar icdadar) (rename cdaddr icdaddr)
80 (rename cddaar icddaar) (rename cddadr icddadr)
81 (rename cdddar icdddar) (rename cddddr icddddr)
82 (rename car+cdr icar+icdr)
83 (rename list-ref ilist-ref)
84
85 (rename first ifirst) (rename second isecond)
86 (rename third ithird)
87 (rename fourth ifourth)
88 (rename fifth ififth)
89 (rename sixth isixth)
90 (rename seventh iseventh)
91 (rename eighth ieighth)
92 (rename ninth ininth)
93 (rename tenth itenth)
94 itake
95 (rename drop idrop)
96 (rename list-tail ilist-tail)
97 (rename take-right itake-right)
98 idrop-right
99 isplit-at
100 (rename last ilast)
101 (rename last-pair last-ipair)
102
103 (rename length ilength)
104 iappend
105 iconcatenate
106 ireverse
107 iappend-reverse
108 izip
109 iunzip1
110 iunzip2
111 iunzip3
112 iunzip4
113 iunzip5
114 (rename count icount)
115
116 imap
117 (rename for-each ifor-each)
118 (rename fold ifold)
119 iunfold
120 (rename pair-fold ipair-fold)
121 (rename reduce ireduce)
122 (rename fold-right ifold-right)
123 iunfold-right
124 (rename pair-fold-right ipair-fold-right)
125 (rename reduce-right ireduce-right)
126 iappend-map
127 (rename pair-for-each ipair-for-each)
128 ifilter-map
129 imap-in-order
130
131 ifilter
132 ipartition
133 iremove
134
135 (rename member imember)
136 (rename memq imemq)
137 (rename memv imemv)
138 ifind
139 (rename find-tail ifind-tail)
140 (rename any iany)
141 (rename every ievery)
142 (rename list-index ilist-index)
143 itake-while
144 (rename drop-while idrop-while)
145 ispan
146 ibreak
147
148 idelete
149 idelete-duplicates
150
151 (rename assoc iassoc)
152 (rename assq iassq)
153 (rename assv iassv)
154 ialist-cons
155 ialist-delete
156
157 replace-icar
158 replace-icdr
159
160 pair->ipair
161 ipair->pair
162 list->ilist
163 ilist->list
164 tree->itree
165 itree->tree
166 gtree->itree
167 gtree->tree
168
169 (rename apply iapply)
170
171 ipair-comparator
172 ilist-comparator
173 (rename make-list-comparator make-ilist-comparator)
174 (rename make-improper-list-comparator make-improper-ilist-comparator)
175 (rename make-car-comparator make-icar-comparator)
176 (rename make-cdr-comparator make-icdr-comparator)
177 (rename make-pair-comparator make-ipair-comparator)
178 ))
179 (select-module scheme.ilist)
180
181 (define-syntax iq
182 (syntax-rules ()
183 [(iq x ...)
184 (gtree->itree '(x ...))]))
185
186 (define (xipair cd ca) (ipair ca cd))
187 (define (ipair* x . xs)
188 (if (null? xs)
189 x
190 (ipair x (apply ipair* xs))))
191 (define (make-ilist n :optional (fill (undefined)))
192 (let loop ([r '()] [n n])
193 (if (<= n 0)
194 r
195 (loop (ipair fill r) (- n 1)))))
196 (define (ilist-tabulate n init-proc)
197 (let loop ([r '()] [n (- n 1)])
198 (if (< n 0)
199 r
200 (loop (ipair (init-proc n) r) (- n 1)))))
201 (define (ilist-copy lis)
202 (fold ipair '() (reverse lis)))
203
204 ;; Almost identical code of iota in src/liblist.scm, but using ipair instead
205 ;; of cons.
206 (define (iiota count :optional (start 0) (step 1))
207 (unless (and (integer? count) (>= count 0))
208 (error "count must be nonnegative integer: " count))
209 (if (and (exact? start) (exact? step))
210 ;; we allow inexact integer as 'count', for the consistency of
211 ;; giota and liota in which we can also accept +inf.0 as count.
212 (let1 count (exact count)
213 (do ([c count (- c 1)]
214 [v (+ start (* (- count 1) step)) (- v step)]
215 [r '() (ipair v r)])
216 [(<= c 0) r]))
217 ;; for inexact numbers, we use multiplication to avoid error accumulation.
218 (do ([c count (- c 1)]
219 [r '() (ipair (+ start (*. (- c 1) step)) r)])
220 [(<= c 0) r])))
221
222 (define (itake lis i)
223 (assume exact-integer? i)
224 (if (<= i 0)
225 '()
226 (ipair (car lis) (itake (cdr lis) (- i 1)))))
227 (define (idrop-right lis i)
228 (assume exact-integer? i)
229 (let rec ([p0 (list-tail lis i)] [p1 lis])
230 (if (pair? p0) (ipair (car p1) (rec (cdr p0) (cdr p1))) '())))
231 (define (isplit-at lis i)
232 (assume exact-integer? i)
233 (let rec ([lis lis] [i i])
234 (if (<= i 0)
235 (values '() lis)
236 (receive (hd tl) (rec (cdr lis) (- i 1))
237 (values (ipair (car lis) hd) tl)))))
238
239 (define (iappend . liss) (iconcatenate liss))
240
241 (define (iconcatenate liss)
242 (match liss
243 ([] '())
244 ([lis] lis)
245 ([lis1 . liss]
246 (let1 tail (iconcatenate liss)
247 (let rec ([lis1 lis1])
248 (if (null? lis1)
249 tail
250 (ipair (car lis1) (rec (cdr lis1)))))))))
251
252 (define (ireverse lis) (fold ipair '() lis))
253
254 (define (iappend-reverse rev-head tail) (fold ipair tail rev-head))
255
256 (define (izip lis1 . liss) (apply imap ilist lis1 liss))
257
258 ;; These are dupe of SRFI-1.SCM except map/cons replaced with imap/ipair
259 (define (iunzip1 lis) (imap car lis))
260
261 (define (iunzip2 lis)
262 (let recur ((lis lis))
263 (if (null-list? lis) (values lis lis) ; Use NOT-PAIR? to handle
264 (let ((elt (car lis))) ; dotted lists.
265 (receive (a b) (recur (cdr lis))
266 (values (ipair (car elt) a)
267 (ipair (cadr elt) b)))))))
268
269 (define (iunzip3 lis)
270 (let recur ((lis lis))
271 (if (null-list? lis) (values lis lis lis)
272 (let ((elt (car lis)))
273 (receive (a b c) (recur (cdr lis))
274 (values (ipair (car elt) a)
275 (ipair (cadr elt) b)
276 (ipair (caddr elt) c)))))))
277
278 (define (iunzip4 lis)
279 (let recur ((lis lis))
280 (if (null-list? lis) (values lis lis lis lis)
281 (let ((elt (car lis)))
282 (receive (a b c d) (recur (cdr lis))
283 (values (ipair (car elt) a)
284 (ipair (cadr elt) b)
285 (ipair (caddr elt) c)
286 (ipair (cadddr elt) d)))))))
287
288 (define (iunzip5 lis)
289 (let recur ((lis lis))
290 (if (null-list? lis) (values lis lis lis lis lis)
291 (let ((elt (car lis)))
292 (receive (a b c d e) (recur (cdr lis))
293 (values (ipair (car elt) a)
294 (ipair (cadr elt) b)
295 (ipair (caddr elt) c)
296 (ipair (cadddr elt) d)
297 (ipair (car (cddddr elt)) e)))))))
298
299
300 (define imap
301 (case-lambda
302 ([proc lis] (fold-right (^[x ys] (ipair (proc x) ys)) '() lis))
303 ([proc lis . liss]
304 (ireverse (apply fold-left (^[ys . xs] (cons (apply proc xs) ys)) '()
305 lis liss)))))
306
307 (define (iunfold p f g seed :optional (tail-gen (^_ '())))
308 (let rec ((seed seed))
309 (if (p seed)
310 (tail-gen seed)
311 (ipair (f seed) (rec (g seed))))))
312
313 (define (iunfold-right p f g seed :optional (ans '()))
314 (let loop ((seed seed) (ans ans))
315 (if (p seed)
316 ans
317 (loop (g seed)
318 (ipair (f seed) ans)))))
319
320 (define (iappend-map proc lis . lists)
321 (iconcatenate (apply map proc lis lists)))
322
323 (define (ifilter-map proc lis . lists)
324 (if (null? lists)
325 (let loop ([lis lis] [r '()])
326 (cond [(null-list? lis) (ireverse r)]
327 [(proc (car lis)) => (^x (loop (cdr lis) (cons x r)))]
328 [else (loop (cdr lis) r)]))
329 (let loop ([liss (cons lis lists)] [r '()])
330 (receive (cars cdrs)
331 ((with-module gauche.internal %zip-nary-args) liss)
332 (cond [(not cars) (ireverse r)]
333 [(apply proc cars) => (^x (loop cdrs (cons x r)))]
334 [else (loop cdrs r)])))))
335
336 (define imap-in-order
337 (case-lambda
338 ([proc lis] (ireverse (fold (^[x ys] (cons (proc x) ys)) '() lis)))
339 ([proc lis . liss]
340 (ireverse (apply fold-left (^[ys . xs] (cons (apply proc xs) ys)) '()
341 lis liss)))))
342
343 (define (ifilter pred lis)
344 (let loop ([lis lis] [r '()])
345 (cond [(null-list? lis) (ireverse r)]
346 [(pred (car lis)) (loop (cdr lis) (cons (car lis) r))]
347 [else (loop (cdr lis) r)])))
348
349 (define (iremove pred l) (ifilter (^x (not (pred x))) l))
350
351 ;;built-in find tolerate improper lists. we're bit more strict here.
352 (define (ifind pred lis)
353 (cond [(null? lis) #f]
354 [(not (pair? lis)) (error "pair expected, but got:" lis)]
355 [(pred (car lis)) (car lis)]
356 [else (ifind pred (cdr lis))]))
357
358 (define (ipartition pred lis)
359 (let rec ([lis lis] [xs '()] [ys '()])
360 (if (null-list? lis)
361 (values (ireverse xs) (ireverse ys))
362 (if (pred (car lis))
363 (rec (cdr lis) (cons (car lis) xs) ys)
364 (rec (cdr lis) xs (cons (car lis) ys))))))
365
366 (define (itake-while pred lis)
367 (cond [(null? lis) '()]
368 [(pred (car lis)) (ipair (car lis) (itake-while pred (cdr lis)))]
369 [else '()]))
370
371 (define (ispan pred lis)
372 (cond [(null? lis) '()]
373 [(pred (car lis))
374 (receive (pre post) (ispan pred (cdr lis))
375 (values (ipair (car lis) pre) post))]
376 [else (values '() lis)]))
377
378 (define (ibreak pred lis) (ispan (complement pred) lis))
379
380 (define (idelete x lis :optional (eq equal?))
381 (if (null? lis)
382 '()
383 (let1 tail (idelete x (cdr lis) eq)
384 (cond [(eq x (car lis)) tail]
385 [(eq? (cdr lis) tail) lis]
386 [else (ipair (car lis) tail)]))))
387
388 (define (idelete-duplicates lis :optional (eq equal?))
389 (cond [(null? lis) lis]
390 [(null? (cdr lis)) lis]
391 [else (let1 tail (idelete (car lis)
392 (idelete-duplicates (cdr lis) eq)
393 eq)
394 (if (eq? tail (cdr lis))
395 lis
396 (ipair (car lis) tail)))]))
397
398 (define (ialist-cons k d alis)
399 (ipair (ipair k d) alis))
400
401 (define (ialist-delete k alis :optional (eq equal?))
402 (cond [(null? alis) '()]
403 [(eq k (caar alis)) (ialist-delete k (cdr alis) eq)]
404 [else (let1 tail (ialist-delete k (cdr alis) eq)
405 (if (eq? tail (cdr alis))
406 alis
407 (ipair (car alis) tail)))]))
408
409 (define (replace-icar p obj) (ipair obj (cdr p)))
410 (define (replace-icdr p obj) (ipair (car p) obj))
411
412 (define (pair->ipair p) (ipair (car p) (cdr p)))
413 (define (ipair->pair p) (cons (car p) (cdr p)))
414
415 (define (list->ilist p)
416 (cond [(null? p) '()]
417 [(ipair? p) (let1 tail (list->ilist (cdr p))
418 (if (eq? (cdr p) tail)
419 p
420 (ipair (car p) tail)))]
421 [(pair? p) (ipair (car p) (list->ilist (cdr p)))]
422 [else p]))
423 (define (ilist->list p)
424 (cond [(null? p) '()]
425 [(pair? p) (let1 tail (ilist->list (cdr p))
426 (if (eq? (cdr p) tail)
427 p
428 (cons (car p) tail)))]
429 [(ipair? p) (cons (car p) (ilist->list (cdr p)))]
430 [else p]))
431
432 (define (tree->itree p)
433 (cond [(ipair? p)
434 (let ([ca (tree->itree (car p))]
435 [cd (tree->itree (cdr p))])
436 (if (and (eq? ca (car p)) (eq? cd (cdr p)))
437 p
438 (ipair ca cd)))]
439 [(pair? p)
440 (ipair (tree->itree (car p)) (tree->itree (cdr p)))]
441 [else p]))
442 (define (itree->tree p)
443 (cond [(pair? p)
444 (let ([ca (itree->tree (car p))]
445 [cd (itree->tree (cdr p))])
446 (if (and (eq? ca (car p)) (eq? cd (cdr p)))
447 p
448 (cons ca cd)))]
449 [(ipair? p)
450 (cons (itree->tree (car p)) (itree->tree (cdr p)))]
451 [else p]))
452
453 ;; Our itree->tree and tree->itree accepts mixed trees, so these are the same.
454 (define (gtree->itree obj) (tree->itree obj))
455 (define (gtree->tree obj) (itree->tree obj))
456
457
458 (define ipair-comparator
459 (make-comparator/compare ipair? #t compare default-hash 'ipair-comparator))
460 (define ilist-comparator
461 (make-comparator/compare list? #t compare default-hash 'ilist-comparator))