Debian Codegraph @

lib/scheme/rlist.scm

raw
1 ;;;
2 ;;; scheme.rlist - Purely Functional Random-Access Pairs and Lists (R7RS Red)
3 ;;;
4 ;;; Copyright (c) 2019-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-101
35 (define-module scheme.rlist
36 (use gauche.record)
37 (use gauche.sequence)
38 (use util.match)
39 (use data.skew-list)
40 (export (rename ra-quote quote)
41 (rename ra-pair? pair?)
42 (rename ra-cons cons)
43 (rename ra-car car)
44 (rename ra-cdr cdr)
45 (rename ra-caar caar)
46 (rename ra-cadr cadr)
47 (rename ra-cddr cddr)
48 (rename ra-cdar cdar)
49 (rename ra-caaar caaar)
50 (rename ra-caadr caadr)
51 (rename ra-caddr caddr)
52 (rename ra-cadar cadar)
53 (rename ra-cdaar cdaar)
54 (rename ra-cdadr cdadr)
55 (rename ra-cdddr cdddr)
56 (rename ra-cddar cddar)
57 (rename ra-caaaar caaaar)
58 (rename ra-caaadr caaadr)
59 (rename ra-caaddr caaddr)
60 (rename ra-caadar caadar)
61 (rename ra-cadaar cadaar)
62 (rename ra-cadadr cadadr)
63 (rename ra-cadddr cadddr)
64 (rename ra-caddar caddar)
65 (rename ra-cdaaar cdaaar)
66 (rename ra-cdaadr cdaadr)
67 (rename ra-cdaddr cdaddr)
68 (rename ra-cdadar cdadar)
69 (rename ra-cddaar cddaar)
70 (rename ra-cddadr cddadr)
71 (rename ra-cddddr cddddr)
72 (rename ra-cdddar cdddar)
73 (rename ra-null? null?)
74 (rename ra-list? list?)
75 (rename ra-list list)
76 (rename ra-make-list make-list)
77 (rename ra-length length)
78 (rename ra-append append)
79 (rename ra-reverse reverse)
80 (rename ra-list-tail list-tail)
81 (rename ra-list-ref list-ref)
82 (rename ra-list-set list-set)
83 (rename ra-list-ref/update list-ref/update)
84 (rename ra-map map)
85 (rename ra-for-each for-each)
86 (rename ra-random-access-list->linear-access-list
87 random-access-list->linear-access-list)
88 (rename ra-linear-access-list->random-access-list
89 linear-access-list->random-access-list)
90 equal? ; builtin equal? works
91 ))
92
93 (select-module scheme.rlist)
94
95 ;; We base on data.skew-list, but we need to extend it to support
96 ;; improper lists. We just keep the last cdr separately.
97
98 (define-record-type <ra-list>
99 %make-ra ra-pair?
100 (spine ra-spine) ; <skew-list>
101 (last-cdr ra-last-cdr)) ; The last cdr
102
103 (define (make-ra spine last-cdr)
104 (if (skew-list-empty? spine)
105 last-cdr
106 (%make-ra spine last-cdr)))
107
108 ;; This is not in SRFI-101, but for the convenience
109 (define-method write-object ((x <ra-list>) port)
110 (display "#,(rlist (" port)
111 (skew-list-fold (ra-spine x)
112 (^[e c]
113 (unless (zero? c) (display " " port))
114 (write e port)
115 (+ c 1))
116 0)
117 (unless (null? (ra-last-cdr x))
118 (display " . " port)
119 (write (ra-last-cdr x) port))
120 (display "))" port))
121
122 (define-reader-ctor 'rlist
123 (^x (ra-linear-access-list->random-access-list x)))
124
125 ;; internal
126 (define (ra-proper? obj)
127 (and (ra-pair? obj) (null? (ra-last-cdr obj))))
128
129 ;; Primitives
130 (define-syntax ra-quote
131 (er-macro-transformer
132 (^[f r c]
133 (define (%x->ra obj)
134 (if (pair? obj)
135 (ra-cons (%x->ra (car obj)) (%x->ra (cdr obj)))
136 obj))
137 (match f
138 [(_ x) (quasirename r
139 `(quote ,(%x->ra x)))]
140 [_ (error "Malformed random-access list quote:" f)]))))
141
142 (define (ra-null? x) (null? x))
143 (define (ra-list? x) (or (null? x) (ra-proper? x)))
144
145 (define (ra-cons x y)
146 (if (ra-pair? y)
147 (make-ra (skew-list-cons x (ra-spine y)) (ra-last-cdr y))
148 (make-ra (skew-list-cons x skew-list-null) y)))
149
150 (define (ra-car obj)
151 (if (ra-pair? obj)
152 (skew-list-car (ra-spine obj))
153 (error "Attempt to take ra-car of " obj)))
154
155 (define (ra-cdr obj)
156 (if (ra-pair? obj)
157 (make-ra (skew-list-cdr (ra-spine obj)) (ra-last-cdr obj))
158 (error "Attempt to take ra-cdr of " obj)))
159
160 (define (%ra-ref obj n)
161 (assume-type obj <ra-list>)
162 (skew-list-ref (ra-spine obj) n))
163 (define (%ra-drop obj n)
164 (assume-type obj <ra-list>)
165 (let1 spine (skew-list-drop (ra-spine obj) n)
166 (make-ra spine (ra-last-cdr obj))))
167
168
169 (define (ra-caar obj) (ra-car (ra-car obj)))
170 (define (ra-cadr obj) (%ra-ref obj 1))
171 (define (ra-cdar obj) (ra-cdr (ra-car obj)))
172 (define (ra-cddr obj) (%ra-drop obj 2))
173
174 (define (ra-caaar obj) (ra-car (ra-caar obj)))
175 (define (ra-caadr obj) (ra-car (ra-cadr obj)))
176 (define (ra-cadar obj) (ra-car (ra-cdar obj)))
177 (define (ra-caddr obj) (%ra-ref obj 2))
178 (define (ra-cdaar obj) (ra-cdr (ra-caar obj)))
179 (define (ra-cdadr obj) (ra-cdr (ra-cadr obj)))
180 (define (ra-cddar obj) (ra-cdr (ra-cdar obj)))
181 (define (ra-cdddr obj) (%ra-drop obj 3))
182
183 (define (ra-caaaar obj) (ra-car (ra-caaar obj)))
184 (define (ra-caaadr obj) (ra-car (ra-caadr obj)))
185 (define (ra-caadar obj) (ra-car (ra-cadar obj)))
186 (define (ra-caaddr obj) (ra-car (ra-caddr obj)))
187 (define (ra-cadaar obj) (ra-car (ra-cdaar obj)))
188 (define (ra-cadadr obj) (ra-car (ra-cdadr obj)))
189 (define (ra-caddar obj) (ra-car (ra-cddar obj)))
190 (define (ra-cadddr obj) (%ra-ref obj 3))
191 (define (ra-cdaaar obj) (ra-cdr (ra-caaar obj)))
192 (define (ra-cdaadr obj) (ra-cdr (ra-caadr obj)))
193 (define (ra-cdadar obj) (ra-cdr (ra-cadar obj)))
194 (define (ra-cdaddr obj) (ra-cdr (ra-caddr obj)))
195 (define (ra-cddaar obj) (ra-cdr (ra-cdaar obj)))
196 (define (ra-cddadr obj) (ra-cdr (ra-cdadr obj)))
197 (define (ra-cdddar obj) (ra-cdr (ra-cddar obj)))
198 (define (ra-cddddr obj) (%ra-drop obj 4))
199
200 (define (ra-list . elts) (ra-linear-access-list->random-access-list elts))
201 (define (ra-make-list n :optional obj)
202 (ra-linear-access-list->random-access-list (make-list n obj)))
203
204 (define (ra-length ra)
205 (cond [(ra-null? ra) 0]
206 [(ra-proper? ra) (skew-list-length (ra-spine ra))]
207 [else
208 (error "Attempt to take length of improper random-access-list:" ra)]))
209
210 (define (ra-length<=? ra k)
211 (if (ra-pair? ra)
212 (skew-list-length<=? (ra-spine ra) k)
213 (zero? k)))
214
215 (define-method object-equal? ((ra1 <ra-list>) (ra2 <ra-list>))
216 (and (equal? (ra-last-cdr ra1) (ra-last-cdr ra2))
217 (equal? (ra-spine ra1) (ra-spine ra2))))
218
219 (define (ra-append obj . objs)
220 (cond [(null? objs) obj]
221 [(null? obj) (apply ra-append objs)]
222 [(ra-proper? obj)
223 (let1 tail (apply ra-append objs)
224 (if (ra-pair? tail)
225 (make-ra (skew-list-append (ra-spine obj)
226 (ra-spine tail))
227 (ra-last-cdr tail))
228 (make-ra (ra-spine obj) tail)))]
229 [else
230 (error "Can't append an improper random-access list:" obj)]))
231
232 (define (ra-reverse ra)
233 (cond [(ra-null? ra) ra]
234 [(ra-proper? ra)
235 (make-ra (list->skew-list (reverse (skew-list->lseq (ra-spine ra))))
236 '())]
237 [else (error "Can't reverse an improper random-access list:" ra)]))
238
239 (define (ra-list-tail obj k)
240 (cond [(zero? k) obj]
241 [(ra-pair? obj)
242 (make-ra (skew-list-drop (ra-spine obj) k)
243 (ra-last-cdr obj))]
244 [else (error "Index out of range:" k)]))
245
246 (define (ra-list-ref ra k)
247 (assume (ra-pair? ra))
248 (skew-list-ref (ra-spine ra) k))
249
250 (define (ra-list-set ra k elt)
251 (assume (ra-pair? ra))
252 (make-ra (skew-list-set (ra-spine ra) k elt)
253 (ra-last-cdr ra)))
254
255 (define (ra-list-ref/update ra k proc)
256 (assume (ra-pair? ra))
257 (let1 v (ra-list-ref ra k)
258 (values v (ra-list-set ra k (proc v)))))
259
260 (define ra-map
261 (case-lambda
262 [(proc ra)
263 ;; fast path
264 (assume (ra-proper? ra))
265 (make-ra (skew-list-map (ra-spine ra) proc) '())]
266 [(proc) (error "At least one random-access list argument required.")]
267 [(proc . ras)
268 (assume (every ra-proper? ras))
269 (assume (apply = (map ra-length ras)))
270 (make-ra (apply map-to <skew-list> proc (map ra-spine ras)) '())]))
271
272 (define ra-for-each
273 (case-lambda
274 [(proc ra)
275 (assume (ra-proper? ra))
276 (skew-list-fold (ra-spine ra) (^[elt _] (proc elt)) #f)
277 (undefined)]
278 [(proc) (error "At least one random-access list argument required.")]
279 [(proc . ras)
280 (assume (every ra-proper? ras))
281 (assume (apply = (map ra-length ras)))
282 (apply for-each proc (map ra-spine ras))]))
283
284 (define (ra-random-access-list->linear-access-list ra)
285 (assume (ra-list? ra))
286 (if (null? ra)
287 ra
288 (skew-list->list (ra-spine ra))))
289
290 (define (ra-linear-access-list->random-access-list lis)
291 (assume (proper-list? lis))
292 (make-ra (list->skew-list lis) '()))