Partitioning a list in Racket

racket, scheme

Solution

Here's how I'd do it:

;; chunkify : (listof number) -> (listof (non-empty-listof number))
;; Split list into maximal contiguous segments.
(define (chunkify lst)
  (cond [(null? lst) null]
        [else (chunkify/chunk (cdr lst) (list (car lst)))]))

;; chunkify/chunk : (listof number) (non-empty-listof number)
;;               -> (listof (non-empty-listof number)
;; Continues chunkifying a list, given a partial chunk.
;; rchunk is the prefix of the current chunk seen so far, reversed
(define (chunkify/chunk lst rchunk)
  (cond [(and (pair? lst)
              (= (car lst) (add1 (car rchunk))))
         (chunkify/chunk (cdr lst)
                         (cons (car lst) rchunk))]
        [else (cons (reverse rchunk) (chunkify lst))]))

It disagrees with your final test case, though:

(chunkify '()) -> '()  ;; not '(()), as you have

I consider my answer more natural; if you really want the answer to be `'(())`, then I'd rename `chunkify` and write a wrapper that handles the empty case specially.

If you prefer to avoid the mutual recursion, you could make the auxiliary function return the leftover list as a second value instead of calling `chunkify` on it, like so:

;; chunkify : (listof number) -> (listof (non-empty-listof number))
;; Split list into maximal contiguous segments.
(define (chunkify lst)
  (cond [(null? lst) null]
        [else
         (let-values ([(chunk tail) (get-chunk (cdr lst) (list (car lst)))])
           (cons chunk (chunkify tail)))]))

;; get-chunk : (listof number) (non-empty-listof number)
;;          -> (values (non-empty-listof number) (listof number))
;; Consumes a single chunk, returns chunk and unused tail.
;; rchunk is the prefix of the current chunk seen so far, reversed
(define (get-chunk lst rchunk)
  (cond [(and (pair? lst)
              (= (car lst) (add1 (car rchunk))))
         (get-chunk (cdr lst)
                    (cons (car lst) rchunk))]
        [else (values (reverse rchunk) lst)]))

Problem

In an application I'm working on in Racket I need to take a list of numbers and partition the list into sub-lists of consecutive numbers: (In the actual application, I'll actually be partitioning pairs consisting of a number and some data, but the principle is the same.) i.e. if my procedure is called `chunkify` then: ``` (chunkify '(1 2 3 5 6 7 9 10 11)) -> '((1 2 3) (5 6 7) (9 10 11)) (chunkify '(1 2 3)) -> '((1 2 3)) (chunkify '(1 3 4 5 7 9 10 11 13)) -> '((1) (3 4 5) (7) (9 10 11) (13)) (chunkify '(1)) -> '((1)) (chunkify '()) -> '(()) ``` etc. I've come up with the following in Racket: ``` #lang racket (define (chunkify lst) (call-with-values (lambda () (for/fold ([chunk '()] [tail '()]) ([cell (reverse lst)]) (cond [(empty? chunk) (values (cons cell chunk) tail)] [(equal? (add1 cell) (first chunk)) (values (cons cell chunk) tail)] [else (values (list cell) (cons chunk tail))]))) cons)) ``` This works just fine, but I'm wondering given the expressiveness of Racket if there isn't a more straightforward simpler way of doing this, some way to get rid of the "call-with-values" and the need to reverse the list in the procedure etc., perhaps some way comepletely different. My first attempt was based very loosely on a pattern with a collector in "The Little Schemer" and that was even less straightforward than the above: ``` (define (chunkify-list lst) (define (lambda-to-chunkify-list chunk) (list chunk)) (let chunkify1 ([list-of-chunks '()] [lst lst] [collector lambda-to-chunkify-list]) (cond [(empty? (rest lst)) (append list-of-chunks (collector (list (first lst))))] [(equal? (add1 (first lst)) (second lst)) (chunkify1 list-of-chunks (rest lst) (lambda (chunk) (collector (cons (first lst) chunk))))] [else (chunkify1 (append list-of-chunks (collector (list (first lst)))) (rest lst) list)]))) ``` What I'm looking for is something simple, concise and straightforward.

Original source