Если вы ищете хвостово-рекурсивное решение, один из подходов заключается в использовании с именем let :
(define (group n xs)
(let loop ([grouped '()] [xs xs])
(if (empty? xs)
(reverse grouped)
(loop (cons (take xs n) grouped)
(drop xs n)))))
Однако это не работает, если xs будет иметь оставшиеся элементы, поэтому нам нужно добавить случай, который проверяет это:
(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))])))
Это работает, но мы можем сделать лучше. Проблема здесь в том, что вычисление (length xs) выполняется за линейное время , потому что единственный способ найти длину простого списка - это просмотреть весь список. Поскольку это внутри цикла, который выполняется несколько раз пропорционально размеру xs, этот код выполняется за квадратичное время, когда его должно быть просто выполнить за линейное время. Мы можем обойти эту проблему, рассчитав длину xs один раз, а затем вычтя из нее n каждую итерацию:
(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))])))
И мы вернулись к линейному времени, сохраняя при этом хвостовую рекурсию и, следовательно, постоянное пространство. Однако мы можем сделать еще одно улучшение. Функция Racket split-at объединяет функции take и drop и возвращает оба списка в виде двух значений. Чтобы использовать функции, возвращающие несколько значений, мы можем использовать 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)))])))
Это немного быстрее, потому что split-at может избежать повторной работы по игнорированию первых n элементов в части drop его функциональности, потому что эти элементы уже будут использованы take. Однако этот код не учитывает неправильный ввод данных пользователем. Если пользователь предоставит n больше, чем длина xs, он выдаст ошибку, когда он должен вернуть (list xs). Это достаточно просто проверить, но наш код очень расширяется вправо со всем этим вложением. В дополнение к проверке этого мы можем разделить цикл на внутренне определенную функцию:
(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))))
Эта функция является хвостовой рекурсивной, не вычисляет (length xs) более одного раза, гарантирует, что (group 4 '(1 2 3)) оценивается как '((1 2 3)), и неравномерная группировка так, что (group 2 '(1 2 3) оценивается до '((1 2) (3)), работает в линейном времени и с постоянной пространство.