我看过一些实现将一个元素添加到列表中的例子,但是它们都没有使用尾递归。如何以函数式的方式实现这样的函数?
(define (append-list lst elem)
expr)
我看过一些实现将一个元素添加到列表中的例子,但是它们都没有使用尾递归。如何以函数式的方式实现这样的函数?
(define (append-list lst elem)
expr)
(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)))))))
(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优化发挥作用的地方。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)实际上做类似事情的一个例子。
很可能编写一个尾递归的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解决方案,它会改变内部列表。
(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(cons head TAIL-EXPR)
这是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)))
我保留返回列表的头部和尾部,并在遍历列表参数时修改尾部。
set!
,set-car!
,set-cdr!
时,这不再被视为一种功能性解决方案,因为您正在更改状态 - 在这种情况下是cons单元。即使在外部看起来是功能性的。 - Óscar Lópezsnoc
操作,或者像你指出的那样使用额外的reverse
。 - Will Ness