core/sequences/sequences.factor

   1 ! Copyright (C) 2005, 2007 Slava Pestov.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 IN: sequences
   4 USING: kernel kernel.private slots.private math math.private ;
   5
   6 MIXIN: sequence
   7
   8 GENERIC: length ( seq -- n ) flushable
   9 GENERIC: set-length ( n seq -- )
  10 GENERIC: nth ( n seq -- elt ) flushable
  11 GENERIC: set-nth ( elt n seq -- )
  12 GENERIC: new ( len seq -- newseq ) flushable
  13 GENERIC: new-resizable ( len seq -- newseq ) flushable
  14 GENERIC: like ( seq exemplar -- newseq ) flushable
  15 GENERIC: clone-like ( seq exemplar -- newseq ) flushable
  16
  17 : new-like ( len exemplar quot -- seq )
  18     over >r >r new r> call r> like ; inline
  19
  20 M: sequence like drop ;
  21
  22 GENERIC: lengthen ( n seq -- )
  23
  24 M: sequence lengthen 2dup length > [ set-length ] [ 2drop ] if ;
  25
  26 : empty? ( seq -- ? ) length zero? ; inline
  27 : delete-all ( seq -- ) 0 swap set-length ;
  28
  29 : first ( seq -- first ) 0 swap nth ; inline
  30 : second ( seq -- second ) 1 swap nth ; inline
  31 : third ( seq -- third ) 2 swap nth ; inline
  32 : fourth  ( seq -- fourth ) 3 swap nth ; inline
  33
  34 : set-first ( first seq -- ) 0 swap set-nth ; inline
  35 : set-second ( second seq -- ) 1 swap set-nth ; inline
  36 : set-third ( third seq -- ) 2 swap set-nth ; inline
  37 : set-fourth  ( fourth seq -- ) 3 swap set-nth ; inline
  38
  39 : push ( elt seq -- ) dup length swap set-nth ;
  40
  41 : bounds-check? ( n seq -- ? )
  42     length 1- 0 swap between? ; inline
  43
  44 TUPLE: bounds-error index seq ;
  45
  46 : bounds-error ( n seq -- * )
  47     \ bounds-error construct-boa throw ;
  48
  49 : bounds-check ( n seq -- n seq )
  50     2dup bounds-check? [ bounds-error ] unless ; inline
  51
  52 MIXIN: immutable-sequence
  53
  54 TUPLE: immutable seq ;
  55
  56 : immutable ( seq -- * ) \ immutable construct-boa throw ;
  57
  58 M: immutable-sequence set-nth immutable ;
  59
  60 INSTANCE: immutable-sequence sequence
  61
  62 <PRIVATE
  63
  64 : max-array-capacity ( -- n )
  65     #! A bit of a pain; can't call cell-bits here
  66     7 getenv 8 * 5 - 2^ 1- ; foldable
  67
  68 PREDICATE: fixnum array-capacity
  69     0 max-array-capacity between? ;
  70
  71 : array-capacity ( array -- n )
  72     1 slot { array-capacity } declare ; inline
  73
  74 : array-nth ( n array -- elt )
  75     swap 2 fixnum+fast slot ; inline
  76
  77 : set-array-nth ( elt n array -- )
  78     swap 2 fixnum+fast set-slot ; inline
  79
  80 GENERIC: resize ( n seq -- newseq ) flushable
  81
  82 ! Unsafe sequence protocol for inner loops
  83 GENERIC: nth-unsafe ( n seq -- elt ) flushable
  84 GENERIC: set-nth-unsafe ( elt n seq -- )
  85
  86 M: sequence nth bounds-check nth-unsafe ;
  87 M: sequence set-nth bounds-check set-nth-unsafe ;
  88
  89 M: sequence nth-unsafe nth ;
  90 M: sequence set-nth-unsafe set-nth ;
  91
  92 ! The f object supports the sequence protocol trivially
  93 M: f length drop 0 ;
  94 M: f nth-unsafe nip ;
  95 M: f like drop dup empty? [ drop f ] when ;
  96
  97 INSTANCE: f immutable-sequence
  98
  99 ! Integers support the sequence protocol
 100 M: integer length ;
 101 M: integer nth-unsafe drop ;
 102
 103 INSTANCE: integer immutable-sequence
 104
 105 : first2-unsafe
 106     [ 0 swap nth-unsafe ] keep 1 swap nth-unsafe ; inline
 107
 108 : first3-unsafe
 109     [ first2-unsafe ] keep 2 swap nth-unsafe ; inline
 110
 111 : first4-unsafe
 112     [ first3-unsafe ] keep 3 swap nth-unsafe ; inline
 113
 114 : exchange-unsafe ( m n seq -- )
 115     [ tuck nth-unsafe >r nth-unsafe r> ] 3keep tuck
 116     >r >r set-nth-unsafe r> r> set-nth-unsafe ; inline
 117
 118 : (head) ( seq n -- from to seq ) 0 spin ; inline
 119
 120 : (tail) ( seq n -- from to seq ) over length rot ; inline
 121
 122 : from-end >r dup length r> - ; inline
 123
 124 : (2sequence)
 125     tuck 1 swap set-nth-unsafe
 126     tuck 0 swap set-nth-unsafe ; inline
 127
 128 : (3sequence)
 129     tuck 2 swap set-nth-unsafe
 130     (2sequence) ; inline
 131
 132 : (4sequence)
 133     tuck 3 swap set-nth-unsafe
 134     (3sequence) ; inline
 135
 136 PRIVATE>
 137
 138 : 2sequence ( obj1 obj2 exemplar -- seq )
 139     2 swap [ (2sequence) ] new-like ; inline
 140
 141 : 3sequence ( obj1 obj2 obj3 exemplar -- seq )
 142     3 swap [ (3sequence) ] new-like ; inline
 143
 144 : 4sequence ( obj1 obj2 obj3 obj4 exemplar -- seq )
 145     4 swap [ (4sequence) ] new-like ; inline
 146
 147 : first2 ( seq -- first second )
 148     1 swap bounds-check nip first2-unsafe ; flushable
 149
 150 : first3 ( seq -- first second third )
 151     2 swap bounds-check nip first3-unsafe ; flushable
 152
 153 : first4 ( seq -- first second third fourth )
 154     3 swap bounds-check nip first4-unsafe ; flushable
 155
 156 : ?nth ( n seq -- elt/f )
 157     2dup bounds-check? [ nth-unsafe ] [ 2drop f ] if ; flushable
 158
 159 MIXIN: virtual-sequence
 160 GENERIC: virtual-seq ( seq -- seq' )
 161 GENERIC: virtual@ ( n seq -- n' seq' )
 162
 163 M: virtual-sequence nth virtual@ nth ;
 164 M: virtual-sequence set-nth virtual@ set-nth ;
 165 M: virtual-sequence nth-unsafe virtual@ nth-unsafe ;
 166 M: virtual-sequence set-nth-unsafe virtual@ set-nth-unsafe ;
 167 M: virtual-sequence like virtual-seq like ;
 168 M: virtual-sequence new virtual-seq new ;
 169
 170 INSTANCE: virtual-sequence sequence
 171
 172 ! A reversal of an underlying sequence.
 173 TUPLE: reversed seq ;
 174
 175 C: <reversed> reversed
 176
 177 M: reversed virtual-seq reversed-seq ;
 178 M: reversed virtual@ reversed-seq [ length swap - 1- ] keep ;
 179 M: reversed length reversed-seq length ;
 180
 181 INSTANCE: reversed virtual-sequence
 182
 183 : reverse ( seq -- newseq ) [ <reversed> ] keep like ;
 184
 185 ! A slice of another sequence.
 186 TUPLE: slice from to seq ;
 187
 188 : collapse-slice ( m n slice -- m' n' seq )
 189     dup slice-from swap slice-seq >r tuck + >r + r> r> ; inline
 190
 191 TUPLE: slice-error reason ;
 192 : slice-error ( str -- * ) \ slice-error construct-boa throw ;
 193
 194 : check-slice ( from to seq -- from to seq )
 195     pick 0 < [ "start < 0" slice-error ] when
 196     dup length pick < [ "end > sequence" slice-error ] when
 197     pick pick > [ "start > end" slice-error ] when ; inline
 198
 199 : <slice> ( from to seq -- slice )
 200     dup slice? [ collapse-slice ] when
 201     check-slice
 202     slice construct-boa ;
 203
 204 M: slice virtual-seq slice-seq ;
 205 M: slice virtual@ [ slice-from + ] keep slice-seq ;
 206 M: slice length dup slice-to swap slice-from - ;
 207
 208 : head-slice ( seq n -- slice ) (head) <slice> ;
 209
 210 : tail-slice ( seq n -- slice ) (tail) <slice> ;
 211
 212 : head-slice* ( seq n -- slice ) from-end head-slice ;
 213
 214 : tail-slice* ( seq n -- slice ) from-end tail-slice ;
 215
 216 INSTANCE: slice virtual-sequence
 217
 218 ! A column of a matrix
 219 TUPLE: column seq col ;
 220
 221 C: <column> column
 222
 223 M: column virtual-seq column-seq ;
 224 M: column virtual@
 225     dup column-col -rot column-seq nth bounds-check ;
 226 M: column length column-seq length ;
 227
 228 INSTANCE: column virtual-sequence
 229
 230 ! One element repeated many times
 231 TUPLE: repetition len elt ;
 232
 233 C: <repetition> repetition
 234
 235 M: repetition length repetition-len ;
 236 M: repetition nth-unsafe nip repetition-elt ;
 237
 238 INSTANCE: repetition immutable-sequence
 239
 240 <PRIVATE
 241
 242 : ((copy)) ( dst i src j n -- dst i src j n )
 243     dup -roll [
 244         + swap nth-unsafe -roll [
 245             + swap set-nth-unsafe
 246         ] 3keep drop
 247     ] 3keep ; inline
 248
 249 : (copy) ( dst i src j n -- dst )
 250     dup 0 <= [ 2drop 2drop ] [ 1- ((copy)) (copy) ] if ; inline
 251
 252 : prepare-subseq ( from to seq -- dst i src j n )
 253     [ >r swap - r> new dup 0 ] 3keep
 254     -rot drop roll length ; inline
 255
 256 : check-copy ( src n dst -- )
 257     over 0 < [ bounds-error ] when
 258     >r swap length + r> lengthen ;
 259
 260 PRIVATE>
 261
 262 : subseq ( from to seq -- subseq )
 263     [ check-slice prepare-subseq (copy) ] keep like ;
 264
 265 : head ( seq n -- headseq ) (head) subseq ;
 266
 267 : tail ( seq n -- tailseq ) (tail) subseq ;
 268
 269 : head* ( seq n -- headseq ) from-end head ;
 270
 271 : tail* ( seq n -- tailseq ) from-end tail ;
 272
 273 : copy ( src i dst -- )
 274     pick length >r 3dup check-copy spin 0 r>
 275     (copy) drop ; inline
 276
 277 M: sequence clone-like
 278     >r dup length r> new [ 0 swap copy ] keep ;
 279
 280 M: immutable-sequence clone-like like ;
 281
 282 : push-all ( src dest -- ) [ length ] keep copy ;
 283
 284 : ((append)) ( seq1 seq2 accum -- accum )
 285     [ >r over length r> copy ] keep
 286     [ 0 swap copy ] keep ; inline
 287
 288 : (append) ( seq1 seq2 exemplar -- newseq )
 289     >r over length over length + r>
 290     [ ((append)) ] new-like ; inline
 291
 292 : (3append) ( seq1 seq2 seq3 exemplar -- newseq )
 293     >r pick length pick length pick length + + r> [
 294         [ >r pick length pick length + r> copy ] keep
 295         ((append))
 296     ] new-like ; inline
 297
 298 : append ( seq1 seq2 -- newseq ) over (append) ;
 299
 300 : 3append ( seq1 seq2 seq3 -- newseq ) pick (3append) ;
 301
 302 : change-nth ( i seq quot -- )
 303     [ >r nth r> call ] 3keep drop set-nth ; inline
 304
 305 : min-length ( seq1 seq2 -- n ) [ length ] 2apply min ; inline
 306
 307 : max-length ( seq1 seq2 -- n ) [ length ] 2apply max ; inline
 308
 309 <PRIVATE
 310
 311 : iterate-seq >r dup length swap r> ; inline
 312
 313 : (each) ( seq quot -- n quot' )
 314     iterate-seq [ >r nth-unsafe r> call ] 2curry ; inline
 315
 316 : (collect) ( quot into -- quot' )
 317     [ >r over slip r> set-nth-unsafe ] 2curry ; inline
 318
 319 : collect ( n quot into -- )
 320     (collect) each-integer ; inline
 321
 322 : map-into ( seq quot into -- )
 323     >r (each) r> collect ; inline
 324
 325 : 2nth-unsafe ( n seq1 seq2 -- elt1 elt2 )
 326     >r over r> nth-unsafe >r nth-unsafe r> ; inline
 327
 328 : (2each) ( seq1 seq2 quot -- n quot' )
 329     >r [ min-length ] 2keep r>
 330     [ >r 2nth-unsafe r> call ] 3curry ; inline
 331
 332 : finish-find ( i seq -- i elt )
 333     over [ dupd nth-unsafe ] [ drop f ] if ; inline
 334
 335 : (find) ( seq quot quot' -- i elt )
 336     pick >r >r (each) r> call r> finish-find ; inline
 337
 338 : (find*) ( n seq quot quot' -- i elt )
 339     >r >r 2dup bounds-check? [
 340         r> r> (find)
 341     ] [
 342         r> r> 2drop 2drop f f
 343     ] if ; inline
 344
 345 : (monotonic) ( seq quot -- ? )
 346     [ 2dup nth-unsafe rot 1+ rot nth-unsafe ]
 347     swap compose curry ; inline
 348
 349 : (interleave) ( n elt between quot -- )
 350     roll zero? [ nip ] [ swapd 2slip ] if call ; inline
 351
 352 PRIVATE>
 353
 354 : each ( seq quot -- )
 355     (each) each-integer ; inline
 356
 357 : reduce ( seq identity quot -- result )
 358     swapd each ; inline
 359
 360 : map-as ( seq quot exemplar -- newseq )
 361     >r over length r> [ [ map-into ] keep ] new-like ; inline
 362
 363 : map ( seq quot -- newseq )
 364     over map-as ; inline
 365
 366 : change-each ( seq quot -- )
 367     over map-into ; inline
 368
 369 : accumulate ( seq identity quot -- final newseq )
 370     swapd [ pick slip ] curry map ; inline
 371
 372 : 2each ( seq1 seq2 quot -- )
 373     (2each) each-integer ; inline
 374
 375 : 2reverse-each ( seq1 seq2 quot -- )
 376     >r [ <reversed> ] 2apply r> 2each ; inline
 377
 378 : 2reduce ( seq1 seq2 identity quot -- result )
 379     >r -rot r> 2each ; inline
 380
 381 : 2map ( seq1 seq2 quot -- newseq )
 382     pick >r (2each) over r>
 383     [ [ collect ] keep ] new-like ; inline
 384
 385 : 2all? ( seq1 seq2 quot -- ? )
 386     (2each) all-integers? ; inline
 387
 388 : find* ( n seq quot -- i elt )
 389     [ (find-integer) ] (find*) ; inline
 390
 391 : find ( seq quot -- i elt )
 392     [ find-integer ] (find) ; inline
 393
 394 : find-last* ( n seq quot -- i elt )
 395     [ nip find-last-integer ] (find*) ; inline
 396
 397 : find-last ( seq quot -- i elt )
 398     [ >r 1- r> find-last-integer ] (find) ; inline
 399
 400 : all? ( seq quot -- ? )
 401     (each) all-integers? ; inline
 402
 403 : push-if ( elt quot accum -- )
 404     >r keep r> rot [ push ] [ 2drop ] if  ; inline
 405
 406 : pusher ( quot -- quot accum )
 407     V{ } clone [ [ push-if ] 2curry ] keep ; inline
 408
 409 : subset ( seq quot -- subseq )
 410     over >r pusher >r each r> r> like ; inline
 411
 412 : monotonic? ( seq quot -- ? )
 413     >r dup length 1- swap r> (monotonic) all? ; inline
 414
 415 : interleave ( seq between quot -- )
 416     [ (interleave) ] 2curry iterate-seq 2each ; inline
 417
 418 : unfold ( pred quot tail -- seq )
 419     V{ } clone [
 420         swap >r [ push ] curry compose r> while
 421     ] keep { } like ; inline
 422
 423 : index ( obj seq -- n )
 424     [ = ] curry* find drop ;
 425
 426 : index* ( obj i seq -- n )
 427     rot [ = ] curry find* drop ;
 428
 429 : last-index ( obj seq -- n )
 430     [ = ] curry* find-last drop ;
 431
 432 : last-index* ( obj i seq -- n )
 433     rot [ = ] curry find-last* drop ;
 434
 435 : contains? ( seq quot -- ? )
 436     find drop >boolean ; inline
 437
 438 : member? ( obj seq -- ? )
 439     [ = ] curry* contains? ;
 440
 441 : memq? ( obj seq -- ? )
 442     [ eq? ] curry* contains? ;
 443
 444 : remove ( obj seq -- newseq )
 445     [ = not ] curry* subset ;
 446
 447 : cache-nth ( i seq quot -- elt )
 448     pick pick ?nth dup [
 449         >r 3drop r>
 450     ] [
 451         drop swap >r over >r call dup r> r> set-nth
 452     ] if ; inline
 453
 454 : mismatch ( seq1 seq2 -- i )
 455     [ min-length ] 2keep
 456     [ 2nth-unsafe = not ] 2curry
 457     find drop ; inline
 458
 459 M: sequence <=>
 460     2dup mismatch
 461     [ -rot 2nth-unsafe <=> ] [ [ length ] compare ] if* ;
 462
 463 : sequence= ( seq1 seq2 -- ? )
 464     2dup [ length ] 2apply number=
 465     [ mismatch not ] [ 2drop f ] if ; inline
 466
 467 : move ( to from seq -- )
 468     pick pick number=
 469     [ 3drop ] [ [ nth swap ] keep set-nth ] if ; inline
 470
 471 : (delete) ( elt store scan seq -- elt store scan seq )
 472     2dup length < [
 473         3dup move
 474         [ nth pick = ] 2keep rot
 475         [ >r >r 1+ r> r> ] unless >r 1+ r> (delete)
 476     ] when ;
 477
 478 : delete ( elt seq -- ) 0 0 rot (delete) nip set-length drop ;
 479
 480 : push-new ( elt seq -- ) [ delete ] 2keep push ;
 481
 482 : add ( seq elt -- newseq )
 483     over >r over length 1+ r> [
 484         [ >r over length r> set-nth-unsafe ] keep
 485         [ 0 swap copy ] keep
 486     ] new-like ;
 487
 488 : add* ( seq elt -- newseq )
 489     over >r over length 1+ r> [
 490         [ 0 swap set-nth-unsafe ] keep
 491         [ 1 swap copy ] keep
 492     ] new-like ;
 493
 494 : seq-diff ( seq1 seq2 -- newseq )
 495     swap [ member? not ] curry subset ;
 496
 497 : peek ( seq -- elt ) dup length 1- swap nth ;
 498
 499 : pop* ( seq -- ) dup length 1- swap set-length ;
 500
 501 : move-backward ( shift from to seq -- )
 502     pick pick number= [
 503         2drop 2drop
 504     ] [
 505         [ >r pick pick + pick r> move >r 1+ r> ] keep
 506         move-backward
 507     ] if ;
 508
 509 : move-forward ( shift from to seq -- )
 510     pick pick number= [
 511         2drop 2drop
 512     ] [
 513         [ >r pick >r dup dup r> + swap r> move 1- ] keep
 514         move-forward
 515     ] if ;
 516
 517 : (open-slice) ( shift from to seq ? -- )
 518     [
 519         >r >r 1- r> 1- r> move-forward
 520     ] [
 521         >r >r over - r> r> move-backward
 522     ] if ;
 523
 524 : open-slice ( shift from seq -- )
 525     pick zero? [
 526         3drop
 527     ] [
 528         pick over length + over >r >r
 529         pick 0 > >r [ length ] keep r> (open-slice)
 530         r> r> set-length
 531     ] if ;
 532
 533 : delete-slice ( from to seq -- )
 534     check-slice >r over >r - r> r> open-slice ;
 535
 536 : delete-nth ( n seq -- )
 537     >r dup 1+ r> delete-slice ;
 538
 539 : replace-slice ( new from to seq -- )
 540     [ >r >r dup pick length + r> - over r> open-slice ] keep
 541     copy ;
 542
 543 : pop ( seq -- elt )
 544     dup length 1- swap [ nth ] 2keep set-length ;
 545
 546 : all-equal? ( seq -- ? ) [ = ] monotonic? ;
 547
 548 : all-eq? ( seq -- ? ) [ eq? ] monotonic? ;
 549
 550 : exchange ( m n seq -- )
 551     pick over bounds-check 2drop 2dup bounds-check 2drop
 552     exchange-unsafe ;
 553
 554 : reverse-here ( seq -- )
 555     dup length dup 2/ [
 556         >r 2dup r>
 557         tuck - 1- rot exchange-unsafe
 558     ] each 2drop ;
 559
 560 : sum-lengths ( seq -- n )
 561     0 [ length + ] reduce ;
 562
 563 : concat ( seq -- newseq )
 564     dup empty? [
 565         drop { }
 566     ] [
 567         [ sum-lengths ] keep
 568         [ first new-resizable ] keep
 569         [ [ over push-all ] each ] keep
 570         first like
 571     ] if ;
 572
 573 : joined-length ( seq glue -- n )
 574     >r dup sum-lengths swap length 1 [-] r> length * + ;
 575
 576 : join ( seq glue -- newseq )
 577     [
 578         2dup joined-length over new-resizable spin
 579         [ dup pick push-all ] [ pick push-all ] interleave drop
 580     ] keep like ;
 581
 582 : padding ( seq n elt quot -- newseq )
 583     >r >r over length [-] dup zero?
 584     [ r> r> 3drop ] [ r> <repetition> r> call ] if ; inline
 585
 586 : pad-left ( seq n elt -- padded )
 587     [ swap dup (append) ] padding ;
 588
 589 : pad-right ( seq n elt -- padded )
 590     [ append ] padding ;
 591
 592 : shorter? ( seq1 seq2 -- ? ) >r length r> length < ;
 593
 594 : head? ( seq begin -- ? )
 595     2dup shorter? [
 596         2drop f
 597     ] [
 598         tuck length head-slice sequence=
 599     ] if ;
 600
 601 : tail? ( seq end -- ? )
 602     2dup shorter? [
 603         2drop f
 604     ] [
 605         tuck length tail-slice* sequence=
 606     ] if ;
 607
 608 : cut-slice ( seq n -- before after )
 609     [ head ] 2keep tail-slice ;
 610
 611 : cut ( seq n -- before after )
 612     [ head ] 2keep tail ;
 613
 614 : cut* ( seq n -- before after )
 615     [ head* ] 2keep tail* ;
 616
 617 <PRIVATE
 618
 619 : (start) ( subseq seq n -- subseq seq ? )
 620     pick length [
 621         >r 3dup r> [ + swap nth-unsafe ] keep rot nth-unsafe =
 622     ] all? nip ; inline
 623
 624 PRIVATE>
 625
 626 : start* ( subseq seq n -- i )
 627     pick length pick length swap - 1+
 628     [ (start) ] find*
 629     swap >r 3drop r> ;
 630
 631 : start ( subseq seq -- i ) 0 start* ; inline
 632
 633 : subseq? ( subseq seq -- ? ) start >boolean ;
 634
 635 : drop-prefix ( seq1 seq2 -- slice1 slice2 )
 636     2dup mismatch [ 2dup min-length ] unless*
 637     tuck tail-slice >r tail-slice r> ;
 638
 639 : unclip ( seq -- rest first )
 640     dup 1 tail swap first ;
 641
 642 : unclip-slice ( seq -- rest first )
 643     dup 1 tail-slice swap first ;
 644
 645 : <flat-slice> ( seq -- slice )
 646     dup slice? [ { } like ] when 0 over length rot <slice> ;
 647     inline
 648
 649 : left-trim ( seq quot -- newseq )
 650     over >r [ not ] compose find drop r> swap
 651     [ tail ] [ dup length tail ] if* ; inline
 652
 653 : right-trim ( seq quot -- newseq )
 654     over >r [ not ] compose find-last drop r> swap
 655     [ 1+ head ] [ 0 head ] if* ; inline
 656
 657 : trim ( seq quot -- newseq )
 658     [ left-trim ] keep right-trim ; inline
 659
 660 : sum ( seq -- n ) 0 [ + ] reduce ;
 661 : product ( seq -- n ) 1 [ * ] reduce ;
 662
 663 : infimum ( seq -- n ) dup first [ min ] reduce ;
 664 : supremum ( seq -- n ) dup first [ max ] reduce ;
 665
 666 : flip ( matrix -- newmatrix )
 667     dup empty? [
 668         dup [ length ] map infimum
 669         [ <column> dup like ] curry* map
 670     ] unless ;
 671
 672 : sequence-hashcode-step ( oldhash newpart -- newhash )
 673     swap [
 674         dup -2 fixnum-shift >fixnum swap 5 fixnum-shift >fixnum
 675         fixnum+fast fixnum+fast
 676     ] keep bitxor ; inline
 677
 678 : sequence-hashcode ( n seq -- x )
 679     0 -rot [
 680         hashcode* >fixnum sequence-hashcode-step
 681     ] curry* each ; inline