scheme - 在 Racket 中对列表进行分区

Question

在我正在 Racket 中处理的应用程序中，我需要获取一个数字列表并将该列表划分为连续数字的子列表:
(在实际应用中，我实际上是对由一个数字和一些数据组成的对进行分区，但原理是一样的。)

即如果我的程序被称为 chunkify然后:

(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 '()) -> '(())  

等等。

我在 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))  

这工作得很好，但我想知道 Racket 的表现力是否有更直接更简单的方法来做到这一点，某种方法来摆脱“call-with-values”和反转列表的需要在程序等方面，也许在某些方面完全不同。

我的第一次尝试非常松散地基于 "The Little Schemer" 中的收集器模式。这比上面的更不简单:

(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)]))) 

我正在寻找的是简单、简洁和直接的东西。

Answer 1

这是我的做法:

;; 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))]))

但是，它不同意您的最终测试用例:

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

我认为我的回答更自然；如果你真的希望答案是 '(()) ，然后我会重命名 chunkify并编写一个专门处理空箱的包装器。

如果你想避免相互递归，你可以让辅助函数返回剩余的列表作为第二个值而不是调用 chunkify在它上面，像这样:

;; 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)]))