问题描述
我已经看到了几个将元素实现 append 到列表中的示例，但是都没有使用 tail recursion .如何以功能样式实现这种功能?
i've seen several examples of implementing append an element to a list, but all are not using tail recursion. how to implement such a function in a functional style?
(define (append-list lst elem)
expr)
推荐答案
以下是 tail递归模态优化优化，从而生成完全尾部递归代码.它复制输入结构，然后以自上而下的方式通过突变将新元素附加到该结构上.由于此突变是针对其内部新创建的数据完成的，因此它在外部仍然可以使用(不更改传递给它的任何数据，除了产生其结果外，没有可观察到的效果):
The following is an implementation of tail recursion modulo cons optimization, resulting in a fully tail recursive code. It copies the input structure and then appends the new element to it, by mutation, in the top-down manner. Since this mutation is done to its internal freshly-created data, it is still functional on the outside (does not alter any data passed into it and has no observable effects except for producing its result):
(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单元.
I like using a "head-sentinel" trick, it greatly simplifies the code at a cost of allocating just one extra cons cell.
此代码使用低级突变原语来完成某些语言(例如Prolog)由编译器自动完成的操作.在TRMC优化假设方案中，我们将能够编写以下尾递归 modulo cons 代码，并让编译器自动将其翻译为与上述代码等效的代码:
This code uses low-level mutation primitives to accomplish what in some languages (e.g. Prolog) is done automatically by a compiler. In TRMC-optimizing hypothetical Scheme, we would be able to write the following tail-recursive modulo cons code, and have a compiler automatically translate it into some equivalent of the code above:
(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优化发挥作用的地方.
If not for the cons operation, append-elt would be tail-recursive. This is where the TRMC optimization comes into play.
2021更新:当然，具有 tail-recursive 函数的全部要点是表示一个循环(以函数样式，是的)，因此例如，例如常见的Lisp(在CLISP实现中)，循环表达式
2021 update: of course the whole point of having a tail-recursive function is to express a loop (in a functional style, yes), and so as an example, in e.g. Common Lisp (in the CLISP implementation), the loop expression
(loop for x in '(1 2) appending (list x))
(这是一种高级规范-y甚至没有以其自身非常特定的方式起作用)被翻译成相同的尾部约束单元跟踪和更改样式:
(which is kind of high-level specification-y if not even functional in its own very specific way) is translated into the same tail-cons-cell tracking and altering style:
[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)的一个示例，它实际上做了类似的事情.
(with the mother of all structure-mutating primitives spelled R.P.L.A.C.D.) so that's one example of a Lisp system (not just Prolog) which actually does something similar.
这篇关于尾递归函数将元素追加到列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！