core/sequences/sequences.factor

   1 ! Copyright (C) 2005, 2008 Slava Pestov, Daniel Ehrenberg.
   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-sequence ( 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-sequence 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 ERROR: bounds-error index seq ;
  45
  46 : bounds-check ( n seq -- n seq )
  47     2dup bounds-check? [ bounds-error ] unless ; inline
  48
  49 MIXIN: immutable-sequence
  50
  51 ERROR: immutable seq ;
  52
  53 M: immutable-sequence set-nth immutable ;
  54
  55 INSTANCE: immutable-sequence sequence
  56
  57 <PRIVATE
  58
  59 : max-array-capacity ( -- n )
  60     #! A bit of a pain; can't call cell-bits here
  61     7 getenv 8 * 5 - 2^ 1- ; foldable
  62
  63 PREDICATE: array-capacity < fixnum
  64     0 max-array-capacity between? ;
  65
  66 : array-capacity ( array -- n )
  67     1 slot { array-capacity } declare ; inline
  68
  69 : array-nth ( n array -- elt )
  70     swap 2 fixnum+fast slot ; inline
  71
  72 : set-array-nth ( elt n array -- )
  73     swap 2 fixnum+fast set-slot ; inline
  74
  75 : dispatch ( n array -- ) array-nth (call) ;
  76
  77 GENERIC: resize ( n seq -- newseq ) flushable
  78
  79 ! Unsafe sequence protocol for inner loops
  80 GENERIC: nth-unsafe ( n seq -- elt ) flushable
  81 GENERIC: set-nth-unsafe ( elt n seq -- )
  82
  83 M: sequence nth bounds-check nth-unsafe ;
  84 M: sequence set-nth bounds-check set-nth-unsafe ;
  85
  86 M: sequence nth-unsafe nth ;
  87 M: sequence set-nth-unsafe set-nth ;
  88
  89 ! The f object supports the sequence protocol trivially
  90 M: f length drop 0 ;
  91 M: f nth-unsafe nip ;
  92 M: f like drop dup empty? [ drop f ] when ;
  93
  94 INSTANCE: f immutable-sequence
  95
  96 ! Integers support the sequence protocol
  97 M: integer length ;
  98 M: integer nth-unsafe drop ;
  99
 100 INSTANCE: integer immutable-sequence
 101
 102 : first2-unsafe
 103     [ 0 swap nth-unsafe ] keep 1 swap nth-unsafe ; inline
 104
 105 : first3-unsafe
 106     [ first2-unsafe ] keep 2 swap nth-unsafe ; inline
 107
 108 : first4-unsafe
 109     [ first3-unsafe ] keep 3 swap nth-unsafe ; inline
 110
 111 : exchange-unsafe ( m n seq -- )
 112     [ tuck nth-unsafe >r nth-unsafe r> ] 3keep tuck
 113     >r >r set-nth-unsafe r> r> set-nth-unsafe ; inline
 114
 115 : (head) ( seq n -- from to seq ) 0 spin ; inline
 116
 117 : (tail) ( seq n -- from to seq ) over length rot ; inline
 118
 119 : from-end >r dup length r> - ; inline
 120
 121 : (2sequence)
 122     tuck 1 swap set-nth-unsafe
 123     tuck 0 swap set-nth-unsafe ; inline
 124
 125 : (3sequence)
 126     tuck 2 swap set-nth-unsafe
 127     (2sequence) ; inline
 128
 129 : (4sequence)
 130     tuck 3 swap set-nth-unsafe
 131     (3sequence) ; inline
 132
 133 PRIVATE>
 134
 135 : 2sequence ( obj1 obj2 exemplar -- seq )
 136     2 swap [ (2sequence) ] new-like ; inline
 137
 138 : 3sequence ( obj1 obj2 obj3 exemplar -- seq )
 139     3 swap [ (3sequence) ] new-like ; inline
 140
 141 : 4sequence ( obj1 obj2 obj3 obj4 exemplar -- seq )
 142     4 swap [ (4sequence) ] new-like ; inline
 143
 144 : first2 ( seq -- first second )
 145     1 swap bounds-check nip first2-unsafe ; flushable
 146
 147 : first3 ( seq -- first second third )
 148     2 swap bounds-check nip first3-unsafe ; flushable
 149
 150 : first4 ( seq -- first second third fourth )
 151     3 swap bounds-check nip first4-unsafe ; flushable
 152
 153 : ?nth ( n seq -- elt/f )
 154     2dup bounds-check? [ nth-unsafe ] [ 2drop f ] if ; flushable
 155
 156 MIXIN: virtual-sequence
 157 GENERIC: virtual-seq ( seq -- seq' )
 158 GENERIC: virtual@ ( n seq -- n' seq' )
 159
 160 M: virtual-sequence nth virtual@ nth ;
 161 M: virtual-sequence set-nth virtual@ set-nth ;
 162 M: virtual-sequence nth-unsafe virtual@ nth-unsafe ;
 163 M: virtual-sequence set-nth-unsafe virtual@ set-nth-unsafe ;
 164 M: virtual-sequence like virtual-seq like ;
 165 M: virtual-sequence new-sequence virtual-seq new-sequence ;
 166
 167 INSTANCE: virtual-sequence sequence
 168
 169 ! A reversal of an underlying sequence.
 170 TUPLE: reversed seq ;
 171
 172 C: <reversed> reversed
 173
 174 M: reversed virtual-seq reversed-seq ;
 175
 176 M: reversed virtual@ reversed-seq [ length swap - 1- ] keep ;
 177
 178 M: reversed length reversed-seq length ;
 179
 180 INSTANCE: reversed virtual-sequence
 181
 182 : reverse ( seq -- newseq ) [ <reversed> ] keep like ;
 183
 184 ! A slice of another sequence.
 185 TUPLE: slice from to seq ;
 186
 187 : collapse-slice ( m n slice -- m' n' seq )
 188     dup slice-from swap slice-seq >r tuck + >r + r> r> ; inline
 189
 190 ERROR: slice-error reason ;
 191
 192 : check-slice ( from to seq -- from to seq )
 193     pick 0 < [ "start < 0" slice-error ] when
 194     dup length pick < [ "end > sequence" slice-error ] when
 195     2over > [ "start > end" slice-error ] when ; inline
 196
 197 : <slice> ( from to seq -- slice )
 198     dup slice? [ collapse-slice ] when
 199     check-slice
 200     slice boa ; inline
 201
 202 M: slice virtual-seq slice-seq ;
 203
 204 M: slice virtual@ [ slice-from + ] keep slice-seq ;
 205
 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-sequence 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 ; inline
 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-sequence [ 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 : prepend ( seq1 seq2 -- newseq ) swap append ; inline
 301
 302 : 3append ( seq1 seq2 seq3 -- newseq ) pick (3append) ;
 303
 304 : change-nth ( i seq quot -- )
 305     [ >r nth r> call ] 3keep drop set-nth ; inline
 306
 307 : min-length ( seq1 seq2 -- n ) [ length ] bi@ min ; inline
 308
 309 : max-length ( seq1 seq2 -- n ) [ length ] bi@ max ; inline
 310
 311 <PRIVATE
 312
 313 : (each) ( seq quot -- n quot' )
 314     >r dup length swap [ nth-unsafe ] curry r> compose ; inline
 315
 316 : (collect) ( quot into -- quot' )
 317     [ >r keep 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> ] bi@ 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 >r dup length swap r> 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 : follow ( obj quot -- seq )
 424     >r [ dup ] r> [ keep ] curry [ ] unfold nip ; inline
 425
 426 : index ( obj seq -- n )
 427     [ = ] with find drop ;
 428
 429 : index* ( obj i seq -- n )
 430     rot [ = ] curry find* drop ;
 431
 432 : last-index ( obj seq -- n )
 433     [ = ] with find-last drop ;
 434
 435 : last-index* ( obj i seq -- n )
 436     rot [ = ] curry find-last* drop ;
 437
 438 : contains? ( seq quot -- ? )
 439     find drop >boolean ; inline
 440
 441 : member? ( obj seq -- ? )
 442     [ = ] with contains? ;
 443
 444 : memq? ( obj seq -- ? )
 445     [ eq? ] with contains? ;
 446
 447 : remove ( obj seq -- newseq )
 448     [ = not ] with subset ;
 449
 450 : cache-nth ( i seq quot -- elt )
 451     2over ?nth dup [
 452         >r 3drop r>
 453     ] [
 454         drop swap >r over >r call dup r> r> set-nth
 455     ] if ; inline
 456
 457 : mismatch ( seq1 seq2 -- i )
 458     [ min-length ] 2keep
 459     [ 2nth-unsafe = not ] 2curry
 460     find drop ; inline
 461
 462 M: sequence <=>
 463     2dup mismatch
 464     [ -rot 2nth-unsafe <=> ] [ [ length ] compare ] if* ;
 465
 466 : sequence= ( seq1 seq2 -- ? )
 467     2dup [ length ] bi@ number=
 468     [ mismatch not ] [ 2drop f ] if ; inline
 469
 470 : sequence-hashcode-step ( oldhash newpart -- newhash )
 471     swap [
 472         dup -2 fixnum-shift-fast swap 5 fixnum-shift-fast
 473         fixnum+fast fixnum+fast
 474     ] keep fixnum-bitxor ; inline
 475
 476 : sequence-hashcode ( n seq -- x )
 477     0 -rot [
 478         hashcode* >fixnum sequence-hashcode-step
 479     ] with each ; inline
 480
 481 M: reversed equal? over reversed? [ sequence= ] [ 2drop f ] if ;
 482
 483 M: slice equal? over slice? [ sequence= ] [ 2drop f ] if ;
 484
 485 : move ( to from seq -- )
 486     2over number=
 487     [ 3drop ] [ [ nth swap ] keep set-nth ] if ; inline
 488
 489 : (delete) ( elt store scan seq -- elt store scan seq )
 490     2dup length < [
 491         3dup move
 492         [ nth pick = ] 2keep rot
 493         [ >r >r 1+ r> r> ] unless >r 1+ r> (delete)
 494     ] when ;
 495
 496 : delete ( elt seq -- ) 0 0 rot (delete) nip set-length drop ;
 497
 498 : push-new ( elt seq -- ) [ delete ] 2keep push ;
 499
 500 : prefix ( seq elt -- newseq )
 501     over >r over length 1+ r> [
 502         [ 0 swap set-nth-unsafe ] keep
 503         [ 1 swap copy ] keep
 504     ] new-like ;
 505
 506 : suffix ( seq elt -- newseq )
 507     over >r over length 1+ r> [
 508         [ >r over length r> set-nth-unsafe ] keep
 509         [ 0 swap copy ] keep
 510     ] new-like ;
 511
 512 : peek ( seq -- elt ) dup length 1- swap nth ;
 513
 514 : pop* ( seq -- ) dup length 1- swap set-length ;
 515
 516 : move-backward ( shift from to seq -- )
 517     2over number= [
 518         2drop 2drop
 519     ] [
 520         [ >r 2over + pick r> move >r 1+ r> ] keep
 521         move-backward
 522     ] if ;
 523
 524 : move-forward ( shift from to seq -- )
 525     2over number= [
 526         2drop 2drop
 527     ] [
 528         [ >r pick >r dup dup r> + swap r> move 1- ] keep
 529         move-forward
 530     ] if ;
 531
 532 : (open-slice) ( shift from to seq ? -- )
 533     [
 534         >r >r 1- r> 1- r> move-forward
 535     ] [
 536         >r >r over - r> r> move-backward
 537     ] if ;
 538
 539 : open-slice ( shift from seq -- )
 540     pick zero? [
 541         3drop
 542     ] [
 543         pick over length + over >r >r
 544         pick 0 > >r [ length ] keep r> (open-slice)
 545         r> r> set-length
 546     ] if ;
 547
 548 : delete-slice ( from to seq -- )
 549     check-slice >r over >r - r> r> open-slice ;
 550
 551 : delete-nth ( n seq -- )
 552     >r dup 1+ r> delete-slice ;
 553
 554 : replace-slice ( new from to seq -- )
 555     [ >r >r dup pick length + r> - over r> open-slice ] keep
 556     copy ;
 557
 558 : pop ( seq -- elt )
 559     dup length 1- swap [ nth ] 2keep set-length ;
 560
 561 : all-equal? ( seq -- ? ) [ = ] monotonic? ;
 562
 563 : all-eq? ( seq -- ? ) [ eq? ] monotonic? ;
 564
 565 : exchange ( m n seq -- )
 566     pick over bounds-check 2drop 2dup bounds-check 2drop
 567     exchange-unsafe ;
 568
 569 : reverse-here ( seq -- )
 570     dup length dup 2/ [
 571         >r 2dup r>
 572         tuck - 1- rot exchange-unsafe
 573     ] each 2drop ;
 574
 575 : sum-lengths ( seq -- n )
 576     0 [ length + ] reduce ;
 577
 578 : concat ( seq -- newseq )
 579     dup empty? [
 580         drop { }
 581     ] [
 582         [ sum-lengths ] keep
 583         [ first new-resizable ] keep
 584         [ [ over push-all ] each ] keep
 585         first like
 586     ] if ;
 587
 588 : joined-length ( seq glue -- n )
 589     >r dup sum-lengths swap length 1 [-] r> length * + ;
 590
 591 : join ( seq glue -- newseq )
 592     [
 593         2dup joined-length over new-resizable spin
 594         [ dup pick push-all ] [ pick push-all ] interleave drop
 595     ] keep like ;
 596
 597 : padding ( seq n elt quot -- newseq )
 598     >r >r over length [-] dup zero?
 599     [ r> r> 3drop ] [ r> <repetition> r> call ] if ; inline
 600
 601 : pad-left ( seq n elt -- padded )
 602     [ swap dup (append) ] padding ;
 603
 604 : pad-right ( seq n elt -- padded )
 605     [ append ] padding ;
 606
 607 : shorter? ( seq1 seq2 -- ? ) >r length r> length < ;
 608
 609 : head? ( seq begin -- ? )
 610     2dup shorter? [
 611         2drop f
 612     ] [
 613         tuck length head-slice sequence=
 614     ] if ;
 615
 616 : tail? ( seq end -- ? )
 617     2dup shorter? [
 618         2drop f
 619     ] [
 620         tuck length tail-slice* sequence=
 621     ] if ;
 622
 623 : cut-slice ( seq n -- before after )
 624     [ head-slice ] 2keep tail-slice ;
 625
 626 : midpoint@ ( seq -- n ) length 2/ ; inline
 627
 628 : halves ( seq -- first second )
 629     dup midpoint@ cut-slice ;
 630
 631 : binary-reduce ( seq start quot -- value )
 632     #! We can't use case here since combinators depends on
 633     #! sequences
 634     pick length dup 0 3 between? [
 635         >fixnum {
 636             [ drop nip ]
 637             [ 2drop first ]
 638             [ >r drop first2 r> call ]
 639             [ >r drop first3 r> bi@ ]
 640         } dispatch
 641     ] [
 642         drop
 643         >r >r halves r> r>
 644         [ [ binary-reduce ] 2curry bi@ ] keep
 645         call
 646     ] if ; inline
 647
 648 : cut ( seq n -- before after )
 649     [ head ] 2keep tail ;
 650
 651 : cut* ( seq n -- before after )
 652     [ head* ] 2keep tail* ;
 653
 654 <PRIVATE
 655
 656 : (start) ( subseq seq n -- subseq seq ? )
 657     pick length [
 658         >r 3dup r> [ + swap nth-unsafe ] keep rot nth-unsafe =
 659     ] all? nip ; inline
 660
 661 PRIVATE>
 662
 663 : start* ( subseq seq n -- i )
 664     pick length pick length swap - 1+
 665     [ (start) ] find*
 666     swap >r 3drop r> ;
 667
 668 : start ( subseq seq -- i ) 0 start* ; inline
 669
 670 : subseq? ( subseq seq -- ? ) start >boolean ;
 671
 672 : drop-prefix ( seq1 seq2 -- slice1 slice2 )
 673     2dup mismatch [ 2dup min-length ] unless*
 674     tuck tail-slice >r tail-slice r> ;
 675
 676 : unclip ( seq -- rest first )
 677     dup 1 tail swap first ;
 678
 679 : unclip-slice ( seq -- rest first )
 680     dup 1 tail-slice swap first ;
 681
 682 : <flat-slice> ( seq -- slice )
 683     dup slice? [ { } like ] when 0 over length rot <slice> ;
 684     inline
 685
 686 : left-trim ( seq quot -- newseq )
 687     over >r [ not ] compose find drop r> swap
 688     [ tail ] [ dup length tail ] if* ; inline
 689
 690 : right-trim ( seq quot -- newseq )
 691     over >r [ not ] compose find-last drop r> swap
 692     [ 1+ head ] [ 0 head ] if* ; inline
 693
 694 : trim ( seq quot -- newseq )
 695     [ left-trim ] keep right-trim ; inline
 696
 697 : sum ( seq -- n ) 0 [ + ] binary-reduce ;
 698 : product ( seq -- n ) 1 [ * ] binary-reduce ;
 699
 700 : infimum ( seq -- n ) dup first [ min ] reduce ;
 701 : supremum ( seq -- n ) dup first [ max ] reduce ;
 702
 703 : flip ( matrix -- newmatrix )
 704     dup empty? [
 705         dup [ length ] map infimum
 706         [ <column> dup like ] with map
 707     ] unless ;