尾递归版本列表附加功能 [英] a tail-recursion version list appending function
问题描述
我看到了几个将append
元素实现到列表中的示例,但都没有使用 tail递归.如何以功能风格实现这样的功能?
i see 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)))))))
我喜欢使用"head-sentinel"技巧,它大大简化了代码,但只分配了一个额外的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) ;; 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优化发挥作用的地方.
If not for the cons
operation, append-elt
would be tail-recursive. This is where the TRMC optimization comes into play.
这篇关于尾递归版本列表附加功能的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!