| 1 |
;;; |
| 2 |
;;; data.skew-list - Skewed Binary Random Access List |
| 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 |
;; Implements SkewList as described in |
| 35 |
;; Chris Okasaki: Purely Functional Data Structures |
| 36 |
;; |
| 37 |
;; Tree a = Leaf a | Node a (Tree a) (Tree a) |
| 38 |
;; SkewList a = SL [(Int, Tree a)] |
| 39 |
|
| 40 |
(define-module data.skew-list |
| 41 |
(use gauche.record) |
| 42 |
(use gauche.sequence) |
| 43 |
(use util.match) |
| 44 |
(use util.queue) |
| 45 |
(export <skew-list> |
| 46 |
skew-list? |
| 47 |
skew-list-empty? |
| 48 |
skew-list-null |
| 49 |
skew-list-cons |
| 50 |
skew-list-car |
| 51 |
skew-list-cdr |
| 52 |
skew-list-ref |
| 53 |
skew-list-set |
| 54 |
skew-list-fold |
| 55 |
skew-list-map |
| 56 |
skew-list-length |
| 57 |
skew-list-length<=? |
| 58 |
list*->skew-list |
| 59 |
list->skew-list |
| 60 |
skew-list->list |
| 61 |
skew-list->generator |
| 62 |
skew-list->lseq |
| 63 |
skew-list-take |
| 64 |
skew-list-drop |
| 65 |
skew-list-split-at |
| 66 |
skew-list-append) |
| 67 |
) |
| 68 |
(select-module data.skew-list) |
| 69 |
|
| 70 |
(define-class <skew-list-meta> (<record-meta>) ()) |
| 71 |
(define-record-type (<skew-list> #f :mixins (<sequence>) |
| 72 |
:metaclass <skew-list-meta>) |
| 73 |
%make-sl skew-list? |
| 74 |
(elements skew-list-elements)) ; [(Int, Tree)]] |
| 75 |
|
| 76 |
(define (SL elts) |
| 77 |
(if (null? elts) |
| 78 |
skew-list-null ;singleton to save allocation |
| 79 |
(%make-sl elts))) |
| 80 |
|
| 81 |
;; We use these frequently. NB: n is always 2^k-1. |
| 82 |
(define-inline (/2 n) (ash n -1)) |
| 83 |
(define-inline (/4 n) (ash n -2)) |
| 84 |
|
| 85 |
;;; |
| 86 |
;;; Primitives |
| 87 |
;;; |
| 88 |
|
| 89 |
(define (skew-list-empty? sl) |
| 90 |
(assume-type sl <skew-list>) |
| 91 |
(null? (skew-list-elements sl))) |
| 92 |
(define skew-list-null (%make-sl '())) |
| 93 |
|
| 94 |
(define (skew-list-cons x y) |
| 95 |
(assume-type y <skew-list>) |
| 96 |
(match (skew-list-elements y) |
| 97 |
[([w1 . t1] [w2 . t2] . ts) |
| 98 |
(if (= w1 w2) |
| 99 |
(SL `([,(+ 1 w1 w2) . (Node ,x ,t1 ,t2)] ,@ts)) |
| 100 |
(SL `([1 . (Leaf ,x)] ,@(skew-list-elements y))))] |
| 101 |
[_ (SL `([1 . (Leaf ,x)] ,@(skew-list-elements y)))])) |
| 102 |
|
| 103 |
(define (skew-list-car sl) |
| 104 |
(assume-type sl <skew-list>) |
| 105 |
(match (skew-list-elements sl) |
| 106 |
[() (error "Attempt to take skew-list-car of empty skew-list")] |
| 107 |
[([_ . ('Leaf x)] . _) x] |
| 108 |
[([_ . ('Node x _ _)] . _) x])) |
| 109 |
|
| 110 |
(define (skew-list-cdr sl) |
| 111 |
(assume-type sl <skew-list>) |
| 112 |
(match (skew-list-elements sl) |
| 113 |
[() (error "Attempt to take skew-list-cdr of empty skew-list")] |
| 114 |
[([_ . ('Leaf _)] . ts) (SL ts)] |
| 115 |
[([w . ('Node x t1 t2)] . ts) |
| 116 |
(SL `([,(/2 w) . ,t1] [,(/2 w) . ,t2] ,@ts))])) |
| 117 |
|
| 118 |
(define (skew-list-ref sl n :optional fallback) |
| 119 |
(define (tree-ref w i t) |
| 120 |
(if (= i 0) |
| 121 |
(cadr t) |
| 122 |
(if (= w 1) |
| 123 |
(if (undefined? fallback) |
| 124 |
(error "index out of range" n) |
| 125 |
fallback) |
| 126 |
(match-let1 ('Node x t1 t2) t |
| 127 |
(let1 w2 (/2 w) |
| 128 |
(if (<= i w2) |
| 129 |
(tree-ref w2 (- i 1) t1) |
| 130 |
(tree-ref w2 (- i 1 w2) t2))))))) |
| 131 |
(define (ref i ts) |
| 132 |
(match ts |
| 133 |
[() (if (undefined? fallback) |
| 134 |
(error "index out of range" n) |
| 135 |
fallback)] |
| 136 |
[((w . t) . ts) |
| 137 |
(if (< i w) (tree-ref w i t) (ref (- i w) ts))])) |
| 138 |
(assume-type sl <skew-list>) |
| 139 |
(ref n (skew-list-elements sl))) |
| 140 |
|
| 141 |
(define (skew-list-set sl n v) |
| 142 |
(define (tree-set w i t) |
| 143 |
(if (= i 0) |
| 144 |
(match t |
| 145 |
[('Leaf _) `(Leaf ,v)] |
| 146 |
[(`Node _ t1 t2) `(Node ,v ,t1 ,t2)]) |
| 147 |
(if (= w 1) |
| 148 |
(error "index out of range" n) |
| 149 |
(match-let1 ('Node x t1 t2) t |
| 150 |
(let1 w2 (/2 w) |
| 151 |
(if (<= i w2) |
| 152 |
`(Node ,x ,(tree-set w2 (- i 1) t1) ,t2) |
| 153 |
`(Node ,x ,t1 ,(tree-set w2 (- i 1 w2) t2)))))))) |
| 154 |
(define (set i ts) |
| 155 |
(match ts |
| 156 |
[() (error "index out of range" n)] |
| 157 |
[((w . t) . ts) |
| 158 |
(if (< i w) |
| 159 |
`((,w . ,(tree-set w i t)) ,@ts) |
| 160 |
`((,w . ,t) ,@(set (- i w) ts)))])) |
| 161 |
(assume-type sl <skew-list>) |
| 162 |
(SL (set n (skew-list-elements sl)))) |
| 163 |
|
| 164 |
;;; |
| 165 |
;;; Conversion |
| 166 |
;;; |
| 167 |
|
| 168 |
;; Input may be an improper list. Returns SL and the last cdr. |
| 169 |
(define (list*->skew-list lis) |
| 170 |
(if (pair? lis) |
| 171 |
(let1 spine-len (let loop ((lis lis) (n 0)) |
| 172 |
(if (pair? lis) (loop (cdr lis) (+ n 1)) n)) |
| 173 |
;; divide n into (k0 k1 ...) where each k is 2^j-1 and decreasing order |
| 174 |
(define (series-2^n-1 n) |
| 175 |
(cond [(= n 0) '()] |
| 176 |
[(= n 1) '(1)] |
| 177 |
[else (let1 k (- (ash 1 (- (integer-length (+ n 1)) 1)) 1) |
| 178 |
(cons k (series-2^n-1 (- n k))))])) |
| 179 |
;; make tree from first n elts of lis (n = 2^j-1) |
| 180 |
;; returns the rest of the lis as well, |
| 181 |
;; being careful not to copy the spine of lis. |
| 182 |
(define (make-tree n lis) |
| 183 |
(if (= n 1) |
| 184 |
(values `(Leaf ,(car lis)) (cdr lis)) |
| 185 |
(let1 n2 (ash (- n 1) -1) |
| 186 |
(receive (t1 rest) (make-tree n2 (cdr lis)) |
| 187 |
(receive (t2 rest) (make-tree n2 rest) |
| 188 |
(values `(Node ,(car lis) ,t1 ,t2) rest)))))) |
| 189 |
;; get reversed series-2^n-1 |
| 190 |
;; returns [(Size . Tree)] and the last cdr of lis |
| 191 |
(define (make-forest ns lis) |
| 192 |
(if (null? ns) |
| 193 |
(values '() lis) |
| 194 |
(receive (tree rest) (make-tree (car ns) lis) |
| 195 |
(receive (forest last-cdr) (make-forest (cdr ns) rest) |
| 196 |
(values (acons (car ns) tree forest) last-cdr))))) |
| 197 |
;; Build one. |
| 198 |
(receive (forest last-cdr) |
| 199 |
(make-forest (reverse (series-2^n-1 spine-len)) lis) |
| 200 |
(values (SL forest) last-cdr))) |
| 201 |
(values skew-list-null lis))) |
| 202 |
|
| 203 |
(define (list->skew-list lis) |
| 204 |
(receive (sl last-cdr) (list*->skew-list lis) |
| 205 |
(unless (null? last-cdr) |
| 206 |
(error "proper list required, but got" lis)) |
| 207 |
sl)) |
| 208 |
|
| 209 |
(define (skew-list->list sl) |
| 210 |
(assume-type sl <skew-list>) |
| 211 |
(reverse (skew-list-fold sl cons '()))) |
| 212 |
|
| 213 |
;;; |
| 214 |
;;; Comparison |
| 215 |
;;; |
| 216 |
|
| 217 |
(define-method object-equal? ((a <skew-list>) (b <skew-list>)) |
| 218 |
(equal? (skew-list-elements a) |
| 219 |
(skew-list-elements b))) |
| 220 |
|
| 221 |
;;; |
| 222 |
;;; Utilities |
| 223 |
;;; |
| 224 |
|
| 225 |
(define (skew-list-fold sl proc seed) |
| 226 |
(define (tree-fold tree seed) |
| 227 |
(match tree |
| 228 |
[('Leaf x) (proc x seed)] |
| 229 |
[('Node x t1 t2) |
| 230 |
(tree-fold t2 (tree-fold t1 (proc x seed)))])) |
| 231 |
(assume-type sl <skew-list>) |
| 232 |
(fold (^[p s] (tree-fold (cdr p) s)) seed (skew-list-elements sl))) |
| 233 |
|
| 234 |
;; NB: We don't support general (n-ary) map; it can be done via |
| 235 |
;; sequence framework. One arg map is worth to support, for we can take |
| 236 |
;; advantage of isomorphism of input and output. |
| 237 |
(define (skew-list-map sl f) |
| 238 |
(define (tmap tree) |
| 239 |
(match tree |
| 240 |
[('Leaf x) `(Leaf ,(f x))] |
| 241 |
[('Node x t0 t1) `(Node ,(f x) ,(tmap t0) ,(tmap t1))])) |
| 242 |
(SL (map (^p `(,(car p) . ,(tmap (cdr p)))) (skew-list-elements sl)))) |
| 243 |
|
| 244 |
(define (skew-list-length sl) |
| 245 |
(assume-type sl <skew-list>) |
| 246 |
(fold (^[p s] (+ (car p) s)) 0 (skew-list-elements sl))) |
| 247 |
|
| 248 |
(define (skew-list-length<=? sl k) |
| 249 |
(assume-type sl <skew-list>) |
| 250 |
(let loop ([es (skew-list-elements sl)] [s 0]) |
| 251 |
(cond [(< k s) #f] |
| 252 |
[(null? es) #t] |
| 253 |
[else (loop (cdr es) (+ s (caar es)))]))) |
| 254 |
|
| 255 |
;; Tree, Int, Int, [Tree] -> [Tree] |
| 256 |
;; Given Tree of size N, returns [Tree] which includes the K-th element |
| 257 |
;; and after. The last input is the tail of the output. |
| 258 |
(define (tree-kth-and-after t n k tail) |
| 259 |
(if (zero? k) |
| 260 |
(cons t tail) |
| 261 |
(match-let1 ('Node _ t1 t2) t |
| 262 |
(let1 m (/2 n) |
| 263 |
(if (<= k m) |
| 264 |
(tree-kth-and-after t1 m (- k 1) (cons t2 tail)) |
| 265 |
(tree-kth-and-after t2 m (- k m 1) tail)))))) |
| 266 |
|
| 267 |
;; [(Int, Tree)], Int -> [(Int, Tree)], Int |
| 268 |
;; Skips elts in seq that doesn't contain K-th element. Returns offset as well. |
| 269 |
(define (skip-seq seq k) |
| 270 |
(if (< k (caar seq)) |
| 271 |
(values seq k) |
| 272 |
(skip-seq (cdr seq) (- k (caar seq))))) |
| 273 |
|
| 274 |
(define (%skew-list-iterator sl start end_) |
| 275 |
(define seq (skew-list-elements sl)) |
| 276 |
(define stack '()) ; [Tree] |
| 277 |
(define end (or end_ (skew-list-length sl))) |
| 278 |
(define pos start) |
| 279 |
(define (next) |
| 280 |
(if (= pos end) |
| 281 |
(values #f #t) |
| 282 |
(match stack |
| 283 |
[() (set! stack (list (cdr (pop! seq)))) (next)] |
| 284 |
[(('Leaf x) . xs) (set! stack xs) (inc! pos)(values x #f)] |
| 285 |
[(('Node x t1 t2) . xs) (set! stack (list* t1 t2 xs)) (inc! pos) (values x #f)]))) |
| 286 |
;; Adjust start point |
| 287 |
(unless (<= start end) (errorf "start ~s is greater than end ~s" start end)) |
| 288 |
(when (< 0 start) |
| 289 |
(receive (seq_ k) (skip-seq seq start) |
| 290 |
(set! stack (tree-kth-and-after (cdar seq_) (caar seq_) k '())) |
| 291 |
(set! seq (cdr seq_)))) |
| 292 |
next) |
| 293 |
|
| 294 |
(define (skew-list->generator sl :optional start end) |
| 295 |
(define iter (%skew-list-iterator sl |
| 296 |
(if (undefined? start) 0 start) |
| 297 |
(if (undefined? end) #f end))) |
| 298 |
(^[] (receive (x eof?) (iter) |
| 299 |
(if eof? (eof-object) x)))) |
| 300 |
|
| 301 |
(define (skew-list->lseq sl :optional start end) |
| 302 |
(define iter (%skew-list-iterator sl |
| 303 |
(if (undefined? start) 0 start) |
| 304 |
(if (undefined? end) #f end))) |
| 305 |
((rec (loop) |
| 306 |
(receive (x eof?) (iter) |
| 307 |
(if eof? |
| 308 |
'() |
| 309 |
(lcons x (loop))))))) |
| 310 |
|
| 311 |
;; take/drop first k elements |
| 312 |
;; In some cases we can share the some of the trees in the original skew-list. |
| 313 |
;; Other than the obvious cases when k is the sum of prefix of the original |
| 314 |
;; seq, there are some nontrivial cases. Suppose 1 < n and n = 2m+1. |
| 315 |
;; If original seq begins with: |
| 316 |
;; [1 n ...] -> We can take 2 and 2+m if m>1 |
| 317 |
;; (e.g. from [1 7 ..] we can take [1 1] and [1 1 3] |
| 318 |
;; [n ...] -> We can take 1, 2, 1+m, 2+m' (where m = 2m'+1) |
| 319 |
;; (e.g. from [15 ...] we can take [1 7], [1 1 3] |
| 320 |
|
| 321 |
(define (%skew-list-splitter sl k rettype) |
| 322 |
;; The branch logic is common among take, drop and split-at. This macro |
| 323 |
;; dispatches the return value. |
| 324 |
(define-syntax ret |
| 325 |
(syntax-rules () |
| 326 |
[(_ taken dropped) |
| 327 |
(case rettype |
| 328 |
[(take) (SL taken)] |
| 329 |
[(drop) (SL dropped)] |
| 330 |
[(split) (cons (SL taken) (SL dropped))])])) |
| 331 |
(define elts (skew-list-elements sl)) |
| 332 |
(define (trivial-prefix) |
| 333 |
(let loop ([seq elts] [sum 0] [i 0]) |
| 334 |
(cond [(= k sum) (ret (take elts i) (drop elts i))] |
| 335 |
[(> k sum) (loop (cdr seq) (+ sum (caar seq)) (+ i 1))] |
| 336 |
[else #f]))) |
| 337 |
(define (special-prefix) |
| 338 |
(match (skew-list-elements sl) |
| 339 |
[((1 . x) (n . ('Node y t1 t2)) . zs) |
| 340 |
(if (= k 2) |
| 341 |
(ret `((1 . ,x) (1 . (Leaf ,y))) |
| 342 |
`((,(/2 n) . ,t1) (,(/2 n) . ,t2) ,@zs)) |
| 343 |
(and (> n 3) |
| 344 |
(= k (+ 2 (/2 n))) |
| 345 |
(ret `((1 . ,x) (1 . (Leaf ,y)) (,(/2 n) . ,t1)) |
| 346 |
`((,(/2 n) . ,t2) ,@zs))))] |
| 347 |
[((n . ('Node x (and ('Node y t11 t12) t1) t2)) . zs) |
| 348 |
(cond [(= k 1) (ret `((1 . (Leaf ,x))) |
| 349 |
`((,(/2 n) . ,t1) (,(/2 n) . ,t2) ,@zs))] |
| 350 |
[(= k 2) (ret `((1 . (Leaf ,x)) (1 . (Leaf ,y))) |
| 351 |
`((,(/4 n) . ,t11) (,(/4 n) . ,t12) (,(/2 n) . ,t2) ,@zs))] |
| 352 |
[(= k (+ 1 (/2 n))) |
| 353 |
(ret `((1 . (Leaf ,x)) (,(/2 n) . ,t1)) |
| 354 |
`((,(/2 n) . ,t2) ,@zs))] |
| 355 |
[(and (> k 3) (= k (+ 2 (/4 n))) ) |
| 356 |
(ret `((1 . (Leaf ,x)) (1 . (Leaf ,y)) (,(/4 n) . ,t11)) |
| 357 |
`((,(/4 n) . ,t12) (,(/2 n) . ,t2) ,@zs))] |
| 358 |
[else #f])] |
| 359 |
[((n . ('Node x ('Leaf y) t2)) . zs) |
| 360 |
(cond [(= k 1) (ret `((1 . (Leaf ,x))) |
| 361 |
`((1 . (Leaf ,y)) (,(/2 n) . ,t2) ,@zs))] |
| 362 |
[(= k 2) (ret `((1 . (Leaf ,x)) (1 . (Leaf ,y))) |
| 363 |
`((,(/2 n) . ,t2) ,@zs))] |
| 364 |
[else #f])])) |
| 365 |
(define (fallback) |
| 366 |
(case rettype |
| 367 |
[(take) (list->skew-list (skew-list->lseq sl 0 k))] |
| 368 |
[(drop) (list->skew-list (skew-list->lseq sl k))] |
| 369 |
[(split) (let1 lis (skew-list->list sl) |
| 370 |
(receive (t d) (split-at lis k) |
| 371 |
(cons (list->skew-list t) (list->skew-list d))))])) |
| 372 |
(or (trivial-prefix) |
| 373 |
(special-prefix) |
| 374 |
(fallback))) |
| 375 |
|
| 376 |
(define (skew-list-take sl k) (%skew-list-splitter sl k 'take)) |
| 377 |
(define (skew-list-drop sl k) (%skew-list-splitter sl k 'drop)) |
| 378 |
(define (skew-list-split-at sl k) |
| 379 |
(let1 r (%skew-list-splitter sl k 'split) |
| 380 |
(values (car r) (cdr r)))) |
| 381 |
|
| 382 |
(define (skew-list-append sl . sls) |
| 383 |
(cond [(null? sls) sl] |
| 384 |
[(skew-list-empty? sl) (apply skew-list-append sls)] |
| 385 |
[(not (skew-list? sl)) (error "argument must be a skew list:" sl)] |
| 386 |
[else (%skew-list-append2 sl (apply skew-list-append sls))])) |
| 387 |
|
| 388 |
(define (%skew-list-append2 sl1 sl2) |
| 389 |
(define (slow-append sl1 sl2) |
| 390 |
(list->skew-list (append (skew-list->list sl1) (skew-list->list sl2)))) |
| 391 |
(match (skew-list-elements sl1) |
| 392 |
[((1 . ('Leaf x))) (skew-list-cons x sl2)] |
| 393 |
[((w0 . t0)) |
| 394 |
(match-let1 ((w1 . t1) . ts) (skew-list-elements sl2) |
| 395 |
(if (= w0 w1) |
| 396 |
(SL (cons (car (skew-list-elements sl1)) (skew-list-elements sl2))) |
| 397 |
(slow-append sl1 sl2)))] |
| 398 |
[_ |
| 399 |
(match-let1 (wz . tz) (last (skew-list-elements sl1)) |
| 400 |
(match-let1 ((w1 . t1) . ts) (skew-list-elements sl2) |
| 401 |
(if (< wz w1) |
| 402 |
(SL (append (skew-list-elements sl1) (skew-list-elements sl2))) |
| 403 |
(slow-append sl1 sl2))))])) |
| 404 |
|
| 405 |
|
| 406 |
;;; |
| 407 |
;;; Collection & sequence protocol |
| 408 |
;;; |
| 409 |
|
| 410 |
(define-method call-with-iterator ((sl <skew-list>) proc) |
| 411 |
(define iter (%skew-list-iterator sl 0 #f)) |
| 412 |
(define-values (item end) (iter)) |
| 413 |
(define (end?) end) |
| 414 |
(define (next) (begin0 item |
| 415 |
(set!-values (item end) (iter)))) |
| 416 |
(proc end? next)) |
| 417 |
|
| 418 |
(define-method call-with-builder ((slc <skew-list-meta>) proc :allow-other-keys) |
| 419 |
(let1 q (make-queue) |
| 420 |
(proc (cut enqueue! q <>) |
| 421 |
(cut list->skew-list (dequeue-all! q))))) |
| 422 |
|
| 423 |
(define-method fold (proc knil (sl <skew-list>)) |
| 424 |
(skew-list-fold sl proc knil)) |
| 425 |
|
| 426 |
(define-method size-of ((sl <skew-list>)) (skew-list-length sl)) |
| 427 |
|
| 428 |
(define-method referencer ((sl <skew-list>)) |
| 429 |
(^[o i] (skew-list-ref o i))) |