List Slices

October 27, 2020

This is an extension of the Standard Prelude function split to multiple sub-lists:

(define (slice widths xs)
  (let loop ((ws widths) (xs xs) (zs (list)))
    (if (null? ws) (reverse zs)
      (let-values (((front back) (split (car ws) xs)))
        (loop (cdr ws) back (cons front zs))))))

And here it is in action:

> (slice '(1 2 3) '(1 2 2 3 3 3))
((1) (2 2) (3 3 3))
> (slice '(1 2 3) '(1 2 2 3))
((1) (2 2) (3))
> (slice '(1 2 3) '(1 2 2))
((1) (2 2) ())
> (slice '(1 2 3) '(1 2 2 3 3 3 4 4 4 4))
((1) (2 2) (3 3 3))

Here’s a way to print a telephone number in a canonical format:

> (let ((xs (map list->string
              (slice '(3 3 4)
                (filter char-numeric?
                  (string->list "123.456.7890"))))))
    (string-append "(" (car xs) ")" (cadr xs) "-" (caddr xs)))
"(123)456-7890"

You can run the program at https://ideone.com/f2xNRM. I’ll probably add this function to the next version of the Standard Prelude.

Pages: 1 2

5 Responses to “List Slices”

  1. chaw said

    Here is an implementation in standard Scheme with no additional dependencies.

    (import (scheme base)
            (scheme write)
            (only (srfi 8) receive))
    
    (define samples ; ((input . output) ...)
      '((((1 2 2 3 3 3) (1 2 3)) . ((1) (2 2) (3 3 3)))
        (((1 2 2 3 3 3) (2 3)) . ((1 2) (2 3 3)))
        (((1 2 2 3 3 3) (2 3 4)) . ((1 2) (2 3 3) (3)))
        (((1 2 2 3 3 3) (2 3 4 2)) . ((1 2) (2 3 3) (3) ()))
        (((1 2 2 3 3 3) (6 6 7)) . ((1 2 2 3 3 3) () ()))
        ((() (6 6 7)) . (() () ()))
        ((() ()) . ())))
    
    ;; Like SRFI-1 split-at, but without error if fewer than k items available
    (define (take-at-most+rest lst k)
      (let loop ((lst lst)
                 (k k)
                 (res '()))
        (if (or (null? lst)
                (not (positive? k)))
            (values (reverse res) lst)
            (loop (cdr lst)
                  (- k 1)
                  (cons (car lst)
                        res)))))
    
    (define (slice/lengths items slice-lengths)
      (let f ((xs items)
              (ls slice-lengths)
              (r '()))
        (if (null? ls)
            (reverse r)
            (receive (taken rest) (take-at-most+rest xs (car ls))
              (f rest
                 (cdr ls)
                 (cons taken r))))))
    
    (define (partial-apply-left proc . args)
      (lambda x (apply proc (append args x))))
    
    (define (demo f)
      (write (equal? (map cdr samples)
                     (map (partial-apply-left apply f) (map car samples))))
      (newline))
    
    (demo slice/lengths)
    

    Output:

    #t
    

  2. Zack said

    Here is my take on this using Julia 1.5: https://pastebin.com/MiMuvK3V

    Pretty straight-forward, through the types need some attention since there is no null for Integers, so I had to use Reals in the output array. Cheers!

  3. Daniel said

    Here are two solutions in Python, the first with explicit calculation of slicing indices, and the second relying on itertools.accumulate.

    def slice1(lst, lengths):
        output = []
        lengths = lengths[::-1]
        start = 0
        while lengths:
            end = start + lengths.pop()
            output.append(lst[start:end])
            start = end
        return output
    
    def slice2(lst, lengths):
        from itertools import accumulate
        acc = [0] + list(accumulate(lengths))
        return [lst[start:end] for start, end in zip(acc, acc[1:])]
    
    print(slice1([1, 2, 2, 3, 3, 3], [1, 2, 3]))
    print(slice1([1, 2, 2, 3], [1, 2, 3]))
    print(slice1([1, 2, 2, 3, 3, 3, 4, 4, 4, 4], [1, 2, 3]))
    
    print(slice2([1, 2, 2, 3, 3, 3], [1, 2, 3]))
    print(slice2([1, 2, 2, 3], [1, 2, 3]))
    print(slice2([1, 2, 2, 3, 3, 3, 4, 4, 4, 4], [1, 2, 3]))
    

    Output:

    [[1], [2, 2], [3, 3, 3]]
    [[1], [2, 2], [3]]
    [[1], [2, 2], [3, 3, 3]]
    [[1], [2, 2], [3, 3, 3]]
    [[1], [2, 2], [3]]
    [[1], [2, 2], [3, 3, 3]]
    
  4. matthew said

    Here’s a couple of Haskell solutions, one using an explicit recursion, the other doing a combined map and fold with mapAccumL:

    splitlist [] _ = []
    splitlist (n:s) t = take n t : splitlist s (drop n t) 
    
    import qualified Data.List
    import qualified Data.Tuple
    
    splitlist counts s = snd (Data.List.mapAccumL f s counts) where
      f s n = Data.Tuple.swap (splitAt n s)
    
  5. Mitchell said

    In common lisp by mapping a recursive function that returns a list of k elements from a list over the list of lengths.

    (defun slice-list (seq n)
    (labels ((rec (s k)
    (if (= k 0)
    nil
    (cons (car s)
    (rec (cdr s) (- k 1))))))
    (let ((offset 0))
    (map 'list
    (lambda (k)
    (let ((new-offset offset))
    (incf offset k)
    (rec (subseq seq new-offset) k)))
    n))))

    (slice-list '(1 2 2 3 3 3) '(1 2 3))
    ; ((1) (2 2) (3 3 3))

    (slice-list '(1 2 2 3 3 3) '(1 2 5))
    ;((1) (2 2) (3 3 3 NIL NIL))

    (slice-list '(1 2 2 3 3 3) '(1 2 1))
    ;((1) (2 2) (3))

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: