尾递归版本列表附加函数

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"技巧,它以分配一个额外的cons单元为代价大大简化了代码.

此代码使用低级突变原语来完成某些语言(例如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 解决方案来改变内部列表。