尾递归函数将元素追加到列表

Question

我见过几个将元素实现到列表的示例，但所有示例都没有使用

尾递归

。如何以函数式风格实现这样的功能？ append

Answer 1

尾递归模cons

优化的实现，产生完全尾递归代码。它复制输入结构，然后通过突变以“自上而下”的方式再追加一个新元素。由于这种突变是对其“内部”新创建的数据进行的，因此它在外部仍然纯粹是功能性的，因为它不会改变传递给它的任何数据，并且除了产生其结果之外没有任何可观察到的影响：

 (define (append-list lst elem)
    expr)

我喜欢使用“head-sentinel”技巧，它极大地简化了代码，但代价是只分配一个额外的

(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 优化假设方案中，我们将能够编写以下尾递归 

modulo cons

代码，并让编译器自动将其转换为上述代码的等效代码：

cons

如果没有

(define (append-elt lst elt)              ;; %% in Prolog:
  (if (null lst)                          ;; app1( [],   E,R) :- Z=[X].
    (list elt)                            ;; app1( [A|D],E,R) :-
    (cons (car lst)                       ;;  R = [A|T], % cons _before_
          (append-elt (cdr lst) elt))))   ;;  app1( D,E,T). % tail call

操作，

cons

将是尾递归。这就是 TRMC 优化发挥作用的地方。

2021 更新：

当然，拥有 tail-recursive 函数的全部目的是表达一个循环（在函数式风格中，是的），举个例子，例如Common Lisp，在 CLISP 实现中，

append-elt

表达式 loop （如果不是以自己非常具体的方式实现

功能

，这也是一种高级规范）被翻译成相同的尾部cons单元跟踪和改变风格：

(loop for x in '(1 2) appending (list x))

（所有结构变异原语的母体拼写为

[20]> (macroexpand '(loop for x in '(1 2) appending (list x)))
(MACROLET ((LOOP-FINISH NIL (SYSTEM::LOOP-FINISH-ERROR)))
 (BLOCK NIL
  (LET ((#:G3047 '(1 2)))
   (PROGN
    (LET ((X NIL))
     (LET ((#:ACCULIST-VAR-30483049 NIL) (#:ACCULIST-VAR-3048 NIL))
      (MACROLET ((LOOP-FINISH NIL '(GO SYSTEM::END-LOOP)))
       (TAGBODY SYSTEM::BEGIN-LOOP (WHEN (ENDP #:G3047) (LOOP-FINISH))
        (SETQ X (CAR #:G3047))
        (PROGN
         (LET ((#:G3050 (COPY-LIST (LIST X))))
          (IF #:ACCULIST-VAR-3048
           (SETF #:ACCULIST-VAR-30483049
            (LAST (RPLACD #:ACCULIST-VAR-30483049 #:G3050)))
           (SETF #:ACCULIST-VAR-30483049
            (LAST (SETF #:ACCULIST-VAR-3048 #:G3050))))))
        (PSETQ #:G3047 (CDR #:G3047)) (GO SYSTEM::BEGIN-LOOP) SYSTEM::END-LOOP
        (MACROLET
         ((LOOP-FINISH NIL (SYSTEM::LOOP-FINISH-WARN) '(GO SYSTEM::END-LOOP)))
         (RETURN-FROM NIL #:ACCULIST-VAR-3048)))))))))) ;
T
[21]>

）

 所以这是 Lisp 系统（不仅仅是 Prolog）的一个例子，它实际上做了类似的事情。

2023 年更新：

 现在 OCaml 也已

有 TRMC，作为

选择加入

。还有榆木。 2024年更新：另一个要搜索的新相关术语是“目的地传递风格”。

嗯，是可以编写尾递归

R.P.L.A.C.D.

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

（为了更好的衡量标准），效率会更低。我想不出另一种

功能性

（例如，不修改输入列表）方法将此过程编写为尾递归，而无需先反转列表。

对于问题的“非功能性”答案，@WillNess 提供了一个很好的方案解决方案，改变内部列表。

这是一个使用延续的函数式尾递归追加elt：

reverse 就性能而言，它与威尔在《球拍与智谋》中的变异版本接近，但在《伊卡洛斯》和《小鸡奥斯卡》中，奥斯卡的相反表现更好。不过，突变始终是表现最好的。不过，我不会使用这个，而是使用 Óscar 条目的一个精简版本，纯粹是因为它更容易阅读。

Answer 3

如果你想要改变性能，我会这样做：

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

您不能天真地这样做，但也请参阅提供 TCMC - Tail Call Modulo Cons 的实现。这允许

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

尾部调用 

(cons head TAIL-EXPR)

Answer 4

这是Lisp，不是Scheme，但我相信你能翻译：

TAIL-EXPR

我保留返回列表的头部

和

Answer 5