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