Функция добавления списка версий хвостовой рекурсии

Question

Я вижу несколько примеров реализации append элемент списка, но все не используют хвостовую рекурсию. Как реализовать такую ​​функцию в функциональном стиле?

 (define (append-list lst elem) expr)

Answer 1

Ниже приведена реализация оптимизации хвостовой рекурсии по модулю, в результате чего получается полностью хвостовой рекурсивный код. Он копирует входную структуру, а затем добавляет новый элемент к нему путем мутации сверху вниз. Поскольку эта мутация выполняется с внутренними вновь созданными данными, она по-прежнему функционирует снаружи (не изменяет никакие данные, передаваемые в нее, и не имеет видимых эффектов, за исключением получения ее результата):

(define (add-elt lst elt)
  (let ((result (list 1)))
    (let loop ((p result) (lst lst))
      (cond 
        ((null? lst) 
           (set-cdr! p (list elt)) 
           (cdr result))
        (else 
           (set-cdr! p (list (car lst)))
           (loop (cdr p) (cdr lst)))))))

Мне нравится использовать трюк "head-sentinel", он значительно упрощает код за счет выделения только одной дополнительной ячейки "против".

Этот код использует низкоуровневые мутационные примитивы для выполнения того, что в некоторых языках (например, Prolog) выполняется автоматически компилятором. В гипотетической схеме, оптимизирующей TRMC, мы могли бы написать следующий код с хвостовой рекурсивностью по модулю и иметь компилятор, автоматически переводящий его в некоторый эквивалент кода выше:

(define (append-elt lst elt)              ;; %% in Prolog:
  (if (null lst)                          ;; app([], X, Z) :- Z=[X].
    (list elt)                            ;; app([A|B], X, Z) :-
    (cons (car lst)                       ;;   Z=[A|Y],         % cons _before_
          (append-elt (cdr lst) elt))))   ;;   app( B, X, Y).   % tail call

Если бы не cons работа, append-elt будет хвост-рекурсивным. Это где оптимизация TRMC вступает в игру.

Answer 2

Ну можно написать хвост-рекурсив append-element процедура...

(define (append-element lst ele)
  (let loop ((lst (reverse lst))
             (acc (list ele)))
    (if (null? lst)
        acc
        (loop (cdr lst) (cons (car lst) acc)))))

... но это более неэффективно с этим reverse брошенный (для хорошей меры). Я не могу придумать другой функциональный (например, без изменения списка ввода) способ написать эту процедуру как хвостовую рекурсию, не обращаясь сначала к списку.

Для нефункционального ответа на вопрос @WillNess предоставил хорошее решение Scheme, изменяющее внутренний список.

Answer 3

Это функциональный хвостовой рекурсивный append-elt, использующий продолжения:

(define (cont-append-elt lst elt)
  (let cont-loop ((lst lst)
                  (cont values))
    (if (null? lst)
        (cont (cons elt '()))
        (cont-loop (cdr lst)
                   (lambda (x) (cont (cons (car lst) x)))))))

По производительности он близок к мутирующему Уиллу в "Ракетке" и "Гамбите", но в "Икаресе" и "Цыпленке" обратный ход Оскара стал лучше. Мутация всегда была лучшим исполнителем. Я бы не использовал это, однако, но небольшую версию записи Оскара, просто потому, что ее легче читать.

(define (reverse-append-elt lst elt)
  (reverse (cons elt (reverse lst))))

И если вы хотите мутировавшего представления, я бы сделал:

(define (reverse!-append-elt lst elt)
  (let ((lst (cons elt (reverse lst))))
     (reverse! lst)
     lst))

Answer 4

Вы не можете наивно, но смотрите также реализации, которые предоставляют TCMC - Tail Call Modulo Минусы. Это позволяет

(cons head TAIL-EXPR)

звонить TAIL-EXPR если минусы сами по себе являются хвостовым вызовом.

Answer 5

Это Лисп, а не Схема, но я уверен, что вы можете перевести:

(defun append-tail-recursive (list tail)
  (labels ((atr (rest ret last)
             (if rest
                 (atr (cdr rest) ret
                      (setf (cdr last) (list (car rest))))
                 (progn
                   (setf (cdr last) tail)
                   ret))))
    (if list
        (let ((new (list (car list))))
          (atr (cdr list) new new))
        tail)))

Я сохраняю голову и хвост списка возврата и изменяю хвост, когда пересекаю аргумент списка.