logo标签列表

尾递归函数向列表追加元素

lispschemerackettail-call-optimizationtailrecursion-modulo-cons
9

我看过一些实现将一个元素添加到列表中的例子，但是它们都没有使用尾递归。如何以函数式的方式实现这样的函数？

 (define (append-list lst elem)
    expr)
5个回答
7
以下是对 尾递归取模 cons 优化的实现，得到完全尾递归的代码。它复制输入结构，然后通过变异方式在 自顶向下 的方式添加一个新元素。由于这个变异操作是针对其内部新创建的数据进行的，因此在外部仍然是纯函数，它不会改变传入的任何数据，并且除了生成结果之外没有任何可观察的影响。
(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)))))))

我喜欢使用“头哨兵”技巧，它极大地简化了代码，只需分配一个额外的cons单元。
这段代码使用低级别的变异原语来完成在某些语言（如Prolog）中由编译器自动完成的操作。在TRMC优化的假设Scheme中，我们可以编写以下尾递归的“模除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操作，append-elt将是尾递归的。这就是TRMC优化发挥作用的地方。
2021年更新：当然，拥有一个尾递归函数的整个目的是表达一个循环（在函数式风格中），所以举个例子，在例如Common Lisp中，在CLISP实现中，loop表达式。
(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 (<b>(#:G3047 '(1 2))</b>)
   (PROGN
    (LET ((X NIL))
     (LET ((<b>#:ACCULIST-VAR-30483049</b> NIL) (<b>#:ACCULIST-VAR-3048</b> NIL))
      (MACROLET ((LOOP-FINISH NIL '(GO SYSTEM::END-LOOP)))
       (TAGBODY SYSTEM::BEGIN-LOOP (WHEN (ENDP #:G3047) (LOOP-FINISH))
        (SETQ X <b>(CAR #:G3047)</b>)
        (PROGN
         (LET (<b>(#:G3050 (COPY-LIST (LIST X)))</b>)
          (IF #:ACCULIST-VAR-3048
           (SETF #:ACCULIST-VAR-30483049
            (LAST <b>(RPLACD #:ACCULIST-VAR-30483049 #:G3050)</b>))
           (SETF #:ACCULIST-VAR-30483049
            (LAST <b>(SETF #:ACCULIST-VAR-3048 #:G3050)</b>)))))
        (PSETQ #:G3047 <b>(CDR #:G3047)</b>) (GO SYSTEM::BEGIN-LOOP) SYSTEM::END-LOOP
        (MACROLET
         ((LOOP-FINISH NIL (SYSTEM::LOOP-FINISH-WARN) '(GO SYSTEM::END-LOOP)))
         (RETURN-FROM NIL <b>#:ACCULIST-VAR-3048</b>)))))))))) ;
T
[21]>

(使用最强大的结构变异原语拼写为R.P.L.A.C.D.) 这就是一个Lisp系统（不仅仅是Prolog）实际上做类似事情的一个例子。

2023年更新：结果OCaml也有了TRMC，作为一种选择。还有Elm。

5

很可能编写一个尾递归的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解决方案，它会改变内部列表。

据我所知，每当您使用set！，set-car！，set-cdr！时，这不再被视为一种功能性解决方案，因为您正在更改状态 - 在这种情况下是cons单元。即使在外部看起来是功能性的。 - Óscar López
我的代码不会改变任何外部程序可观察到的状态。它也不会原地修改输入列表。 - Will Ness
我重新阅读了问题，是的，我的实现不是问题所要求的“函数式风格的实现”。这是无法做到的，除非有一个内置的 snoc 操作，或者像你指出的那样使用额外的 reverse。 - Will Ness
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)))))))

就性能而言，它与Racket和Gambit中Will的那个可变版本接近，但在Ikarus和Chicken中，Óscar的reverse表现更好。不过，变异始终是最佳表现者。然而，我不会使用这个，而是使用稍微修改过的Óscar的条目，纯粹是因为它更易于阅读。

(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))
对于为了效率而编写的难以阅读的函数，您可以始终添加解释性注释，例如 foldr (:) [a] xs，或 (set-cdr! (last-pair (copy-list xs)) (list a))，或 == (reverse (cons elt (reverse lst)))，或用英语。-- 顶部向下 O(1) 额外空间 TRMC 代码的重点在于，我们可以比交换额外的 O(n) 堆栈结构换取额外的 O(n) 延续结构更好，((((id.(1:)).(2:)).(3:)).(4:)) [5]。实际上，为了构建结果，这执行了两个 O(n) 通行证，而其 Haskell 等效项执行了三个通行证，而顶部向下 TRMC 代码则只需一次通行证。 - Will Ness
编译器实际上在幕后进行变异，所以很遗憾它不像Prolog那样自动执行TRMC优化。如果您查看SRFI-1参考实现，您会发现所有有序程序都会在给定足够大的列表时导致堆栈崩溃。 - Sylwester
是的，我一直觉得这很奇怪。也许他们只是提供这个参考实现作为结果必须是什么的描述；一个规范。另外，TRMC易于看作是带有累加器的尾递归；只是通过set-cdr！操作最后一对来完成累加。 - Will Ness
2
你不能简单地实现尾调用优化，但也可以看到一些提供TCMC（Tail Call Modulo Cons）的实现。这允许…
(cons head TAIL-EXPR)

如果cons本身是尾递归，则需要尾调用TAIL-EXPR。
是的，但之后你必须再次反转列表。TCMC 的重点在于您无需在最后再次反转列表，并且它提供了与命令式语言相同的性能。 - LeoNerd
是的，TCMC 是一个相当不错的改进。 - Vatine
@Vatine TRMC 也可以被看作是累积的 - 它只是通过 nconcing 进行累积。C 可以做到，Scheme 也可以做到。Prolog 会自动进行优化。 - Will Ness
1

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

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

我保留返回列表的头部和尾部，并在遍历列表参数时修改尾部。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接