Partitionner une liste dans Racket

Question

Dans une application sur laquelle je travaille dans Racket, je dois prendre une liste de nombres et partitionner la liste en sous-listes de nombres consécutifs: (Dans l'application, je serai effectivement partitionner paires constituées d'un nombre et des données, mais le principe est le même)

à savoir si ma procédure est appelée chunkify alors:.

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

Je suis venu avec ce qui suit dans 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)) 

Cela fonctionne très bien, mais je me demande donné l'expressivité de Racket s'il n'y a pas une façon plus simple plus simple de le faire, une certaine façon de se débarrasser des « call-with-valeurs » et la nécessité d'inverser la liste dans la procédure etc., peut-être d'une manière tout à fait différente.

Ma première tentative a été plus ou moins basé sur un modèle avec un collecteur "The Little Schemer" et qui était encore moins simple que ce qui précède:

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

Ce que je suis à la recherche est quelque chose de simple, concis et simple.

Answer 1

Voilà comment je le ferais:

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

Il est en désaccord avec votre cas de test final, bien que:

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

Je considère ma réponse plus naturelle; Si vous voulez vraiment que la réponse soit '(()), alors je renommerais chunkify et écrirais un emballage qui manipule le cas vide particulièrement.

Si vous préférez éviter la récursion mutuelle, vous pouvez faire la fonction auxiliaire retourne la liste des restes comme une deuxième valeur au lieu d'appeler chunkify sur elle, comme ceci:

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

Je peux penser à une solution simple et directe à l'aide d'une procédure unique avec seulement les opérations de liste primitives et récursion arrière (pas values, let-values, call-with-values) - et il est assez efficace. Cela fonctionne avec tous vos cas de test, au prix d'ajouter quelques expressions if lors de l'initialisation pour gérer le cas de liste vide. Il est à vous de décider si cela est concis:

(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

Encore une autre façon de le faire .

#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

Je veux jouer.

À la base, ce n'est pas vraiment quelque chose de très différent de ce qui est proposé, mais il le met en termes de la boucle for/fold. J'ai cultivé pour aimer les boucles for car je pense qu'ils font beaucoup de code "visible" (pas nécessairement lisible) .Cependant, (OMI - oups) au cours des premières étapes de se familiariser avec raquette/schéma, je pense qu'il est préférable de s'en tenir à des expressions récursives.

(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

Voilà ma version:

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

Il travaille également pour le dernier cas de test.