9

我见过几个append将元素实现到列表的示例，但都没有使用尾递归。如何以功能风格实现这样的功能？

 (define (append-list lst elem)
    expr)
4

5 回答 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)))))))

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

此代码使用低级突变原语来完成某些语言（例如 Prolog）中由编译器自动完成的工作。在 TRMC 优化假设方案中，我们将能够编写以下尾递归模 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 for x in '(1 2) appending (list x))

（这是一种高级规范——如果它甚至没有以它自己非常具体的方式发挥作用）被翻译成相同的 tail-cons-cell 跟踪和改变风格：

[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]>

（所有结构变异原语之母拼写为R.P.L.A.C.D.）所以这是 Lisp 系统（不仅仅是 Prolog）的一个例子，它实际上做了类似的事情。

于 2012-11-06T17:52:35.973 回答
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 解决方案来改变内部列表。

于 2012-11-06T17:17:10.860 回答
3

这是一个使用延续的功能性尾递归附加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 中的变异，但在 Ikarus 和 Chicken Óscar 的反面中表现更好。突变总是表现最好的。然而，我不会使用这个，而是 Ó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))
于 2013-07-20T21:38:57.713 回答
2

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

(cons head TAIL-EXPR)

TAIL-EXPR如果 cons 本身是尾调用，则进行尾调用。

于 2012-11-06T18:12:36.123 回答
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)))

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

于 2012-11-06T17:40:54.553 回答