Partycjonowanie listy w Rakiecie

Question

W aplikacji, nad którą pracuję w Racket, muszę wziąć listę liczb i podzielić listę na pod-listy kolejnych numerów: (W aktualnym zgłoszeniu, będę faktycznie partycjonowanie par składających się z szeregu, a niektóre dane, ale zasada jest taka sama)

czyli jeśli mój procedura nazywa chunkify potem.

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

itp

mam wymyślić następujące w Rakiecie:

#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)) 

Działa to dobrze, ale zastanawiam względu na wyrazistość rakiety, jeśli nie jest to bardziej oczywiste prostszy sposób to zrobić, jakiś sposób, aby pozbyć się „wartości nazywają-z” i konieczność odwrócenia listy w procedurze itp., być może w pewien sposób zupełnie odmienny.

Moja pierwsza próba była oparta na bardzo luźno wzór z kolektora w "The Little Schemer" i to nawet mniej oczywiste niż powyższe:

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

Co szukam jest coś proste, zwięzłe i jednoznaczne.

Answer 1

Oto jak zrobiłbym to:

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

że nie zgadza się z końcowego testu, choć:

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

Uważam, że moja odpowiedź jest bardziej naturalna; jeśli naprawdę chcesz, aby odpowiedź brzmiała: '(()), zmieniam nazwę na chunkify i napiszę opakowanie, które specjalnie obsługuje pustą obudowę.

Jeśli wolisz, aby uniknąć wzajemnej rekursji, można sprawić, że funkcja pomocnicza powrócić listę resztki jako drugą wartość zamiast dzwonić chunkify na nim tak:

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

Answer 2

mogę myśleć o prostym, proste rozwiązanie z zastosowaniem procedury jednego z prymitywnych tylko lista operacji i ogon rekursji (nr values, let-values, call-with-values) - i to całkiem wydajny. Działa z wszystkimi testowymi przypadkami, kosztem dodania kilku wyrażeń if podczas inicjowania obsługi pustej listy list. To do ciebie, aby zdecydować, czy to jest zwięzły:

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

Answer 3

Jeszcze innym sposobem, aby to zrobić .

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

Answer 4

Chcę grać.

W rzeczywistości nie jest to coś, co znacznie różni się od tego, co oferuje , ale zawiera je w kategoriach pętli for/fold. Mam wyhodowany, aby polubić pętle for, ponieważ myślę, że powodują one dużo "widoczny" (niekoniecznie czytelny) kod.Jednak (IMO - ups) podczas wczesnych etapów uzyskiwania komfortu z rakietką/schematem uważam, że najlepiej trzymać się wyrażeń rekursywnych.

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

Answer 5

Oto moja wersja:

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

Działa również na tym ostatnim przypadku testowego.