一尾递归版本列表追加功能(a tail-recursion version list appendi

我看到实施的若干实例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)))))))

我喜欢用一个“头哨兵”的把戏，它大大简化了代码的分配只是一个额外的利弊电池的成本。

此代码使用低级别的突变原语来完成的某些语言（如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提供一个很好的解决方案的变异内部列表。

Answer 3:

你不能天真，但也看到，提供TCMC实现 - 尾调用模缺点。这使

(cons head TAIL-EXPR)

到尾部调用TAIL-EXPR如果缺点本身是一个尾部调用。

Answer 4:

这是一个功能性的，尾递归使用continuation追加-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)))))))

性能方面它靠近威尔的突变一个球拍和开局，但在的Ikarus和鸡奥斯卡的反向表现得好。突变总是表现最好不过。我不会用不过这一点，但奥斯卡的条目略有版本，纯粹是因为它更容易阅读。

(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 5:

这是Lisp的，没有计划，但我相信你能翻译：

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

我保持头部和返回列表的尾部和修改尾巴，我遍历列表的说法。

文章来源: a tail-recursion version list appending function