11

私が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の表現力を考えると、これを行うためのより簡単で簡単な方法、「値を使用した呼び出し」を取り除く方法、およびリストを逆にする必要があるかどうか疑問に思います。手順などでは、おそらく何らかの形で完全に異なります。

私の最初の試みは、 「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)])))

私が探しているのは、シンプルで簡潔でわかりやすいものです。

4

5 に答える 5

4

これが私がそれをする方法です：

;; 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して、空のケースを特別に処理するラッパーを作成します。

相互再帰を避けたい場合は、次のように、補助関数が残りのリストを呼び出す代わりに、2番目の値として返すようにすることができます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)]))
于 2012-04-29T04:15:49.743 に答える
3

valuesプリミティブリスト操作と末尾再帰（no 、、）のみを使用する単一のプロシージャを使用する単純で単純なソリューションを考えることができます。これlet-valuesはcall-with-values非常に効率的です。if空のリストケースを処理するための初期化中にいくつかの式を追加するという犠牲を払って、すべてのテストケースで機能します。これが簡潔であるかどうかを判断するのはあなた次第です。

(define (chunkify lst)
  (let ((lst (reverse lst))) ; it's easier if we reverse the input list first
    (let loop ((lst (if (null? lst) '() (cdr lst)))        ; list to chunkify
               (cur (if (null? lst) '() (list (car lst)))) ; current sub-list
               (acc '()))                                  ; accumulated answer
      (cond ((null? lst)                    ; is the input list empty?
             (cons cur acc))
            ((= (add1 (car lst)) (car cur)) ; is this a consecutive number?
             (loop (cdr lst) (cons (car lst) cur) acc))
            (else                           ; time to create a new sub-list
             (loop (cdr lst) (list (car lst)) (cons cur acc)))))))
于 2012-04-29T02:18:48.587 に答える
3

それを行うためのさらに別の方法。

#lang racket

(define (split-between pred xs)
  (let loop ([xs xs]
             [ys '()]
             [xss '()])
    (match xs
      [(list)                 (reverse (cons (reverse ys) xss))]
      [(list x)               (reverse (cons (reverse (cons x ys)) xss))]
      [(list x1 x2 more ...)  (if (pred x1 x2) 
                                  (loop more (list x2) (cons (reverse (cons x1 ys)) xss))
                                  (loop (cons x2 more) (cons x1 ys) xss))])))

(define (consecutive? x y)
  (= (+ x 1) y))

(define (group-consecutives xs)
  (split-between (λ (x y) (not (consecutive? x y))) 
                 xs))


(group-consecutives '(1 2 3 5 6 7 9 10 11))
(group-consecutives '(1 2 3))
(group-consecutives '(1 3 4 5 7 9 10 11 13))
(group-consecutives '(1))
(group-consecutives '())
于 2012-04-29T15:26:35.357 に答える
1

これが私のバージョンです：

(define (chunkify lst)
  (let loop ([lst lst] [last #f] [resint '()] [resall '()])
    (if (empty? lst) 
        (append resall (list (reverse resint)))
        (begin
          (let ([ca (car lst)] [cd (cdr lst)])
            (if (or (not last) (= last (sub1 ca)))
                (loop cd ca (cons ca resint) resall)
                (loop cd ca (list ca) (append resall (list (reverse resint))))))))))

最後のテストケースでも機能します。

于 2012-05-06T11:26:03.667 に答える
1

私は遊びたいです。

コアでは、これは実際に提供されているものと大きく異なるものではありませんが、for/foldループの観点からはそれを示しています。forループは、はるかに「表示可能」な（必ずしも読み取り可能である必要はない）コードになると思うので、私はforループが好きになりました。ただし、（IMO --oops）ラケット/スキームに慣れるための初期段階では、再帰的な表現に固執するのが最善だと思います。

(define (chunkify lst)  
    (define-syntax-rule (consecutive? n chunk)     
      (= (add1 (car chunk)) n))
    (if (null? lst)
        'special-case:no-chunks
        (reverse 
         (map reverse
              (for/fold  ([store    `((,(car lst)))])
                         ([n         (cdr lst)])
                 (let*([chunk   (car store)])
                   (cond 
                    [(consecutive? n chunk)
                        (cons  (cons n chunk)  (cdr store))]
                    [else
                        (cons  (list n)  (cons chunk (cdr store)))])))))))


(for-each
 (ƛ (lst)  
    (printf "input   :  ~s~n" lst)
    (printf "output  :  ~s~n~n" (chunkify lst)))
 '((1 2 3 5 6 7 9 10 11)
   (1 2 3)
   (1 3 4 5 7 9 10 11 13)
   (1)
   ()))
于 2012-05-05T23:21:08.747 に答える