Wenn Sie nach einer tail-recursiven Lösung suchen, ist ein Ansatz, die benannt lassen :
(define (group n xs)
(let loop ([grouped '()] [xs xs])
(if (empty? xs)
(reverse grouped)
(loop (cons (take xs n) grouped)
(drop xs n)))))
Dies schlägt jedoch fehl, wenn xs würden Elemente übrig bleiben, also müssen wir einen Fall hinzufügen, der dies überprüft:
(define (group n xs)
(let loop ([grouped '()] [xs xs])
(cond
[(empty? xs)
(reverse grouped)]
[(<= (length xs) n)
(loop (cons xs grouped) '())]
[else (loop (cons (take xs n) grouped)
(drop xs n))])))
Das funktioniert, aber wir können es besser machen. Das Problem dabei ist, dass die Berechnung (length xs) läuft ein lineare Zeit Denn die einzige Möglichkeit, die Länge einer einfachen Liste zu ermitteln, besteht darin, die gesamte Liste abzuarbeiten. Da dies innerhalb einer Schleife geschieht, die proportional zur Größe der Liste xs Dieser Code läuft in quadratischer Zeit, obwohl er eigentlich in linearer Zeit zu erledigen wäre. Wir können dieses Problem umgehen, indem wir die Länge von xs einmal und subtrahiert dann n von ihm bei jeder Iteration:
(define (group n xs)
(let loop ([grouped '()] [xs xs] [l (length xs)])
(cond
[(empty? xs)
(reverse grouped)]
[(<= l n)
(loop (cons xs grouped) '() 0)]
[else (loop (cons (take xs n) grouped)
(drop xs n)
(- l n))])))
Und schon sind wir wieder bei linearer Zeit, wobei die Schwanzrekursion und damit der Platzbedarf konstant bleiben. Es gibt jedoch noch eine weitere Verbesserung, die wir vornehmen können. Die Racket-Funktion split-at kombiniert die Funktionalität von take y drop und gibt beide Listen als zwei Werte zurück. Um Funktionen, die mehrere Werte zurückgeben, zu verwenden, können wir let-values :
(define (group n xs)
(let loop ([grouped '()] [xs xs] [l (length xs])
(cond
[(empty? xs)
(reverse grouped)]
[(<= l n)
(loop (cons xs grouped) '() 0)]
[else (let-values ([(taken dropped) (split-at xs n)])
(loop (cons taken grouped)
dropped
(- l n)))])))
Dies ist etwas schneller, weil split-at kann die Wiederholung der Arbeit des Ignorierens des ersten n Elemente im drop Teil der Funktionalität, da diese Elemente bereits von take . Dieser Code berücksichtigt jedoch keine falschen Benutzereingaben. Wenn ein Benutzer eine n größer als die Länge von xs wird eine Fehlermeldung ausgegeben, obwohl sie eigentlich Folgendes zurückgeben sollte (list xs) . Es ist einfach genug, dies zu überprüfen, aber unser Code wird durch die Verschachtelung nach rechts hin furchtbar lang. Zusätzlich zu dieser Überprüfung können wir die Schleife in eine intern definierte Funktion aufteilen:
(define (group n xs)
(define (loop grouped xs l)
(cond
[(empty? xs)
(reverse grouped)]
[(<= l n)
(loop (cons xs grouped) '() 0)]
[else (let-values ([(taken dropped) (split-at xs n)])
(loop (cons taken grouped)
dropped
(- l n)))]))
(let ([l (length xs)])
(if (>= n l)
(list xs)
(loop '() xs l))))
Diese Funktion ist schwanzrekursiv, berechnet nicht (length xs) mehr als einmal, stellt sicher, dass (group 4 '(1 2 3)) wertet aus zu '((1 2 3)) und eine ungerade Gruppierung, so dass (group 2 '(1 2 3) wertet aus zu '((1 2) (3)) und läuft in linearer Zeit und konstantem Raum.
