a tail-recursion version list appending function

问题:

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)

回答1:

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

I like using a "head-sentinel" trick, it greatly simplifies the code at a cost of allocating just one extra cons cell.

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

If not for the cons operation, append-elt would be tail-recursive. This is where the TRMC optimization comes into play.

回答2:

Well it is possible to write a tail-recursive append-element procedure...

(define (append-element lst ele)
  (let loop ((lst (reverse lst))
             (acc (list ele)))
    (if (null? lst)
        acc
        (loop (cdr lst) (cons (car lst) acc)))))

... but it's more inefficient with that reverse thrown in (for good measure). I can't think of another functional (e.g., without modifying the input list) way to write this procedure as a tail-recursion without reversing the list first.

For a non-functional answer to the question, @WillNess provided a nice Scheme solution mutating an internal list.

回答3:

You can't naively, but see also implementations that provide TCMC - Tail Call Modulo Cons. That allows

(cons head TAIL-EXPR)

to tail-call TAIL-EXPR if the cons itself is a tail-call.

回答4:

This is a functional, tail recursive append-elt using continuations:

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

Performance-wise it's close to Will's mutating one in Racket and Gambit but in Ikarus and Chicken Óscar's reverse did better. Mutation was always the best performer though. I wouldn't have used this however, but a slight version of Óscar's entry, purely because it is easier to read.

(define (reverse-append-elt lst elt)
  (reverse (cons elt (reverse lst))))

And if you want mutating performance I would have done:

(define (reverse!-append-elt lst elt)
  (let ((lst (cons elt (reverse lst))))
     (reverse! lst)
     lst))

回答5:

This is Lisp, not Scheme, but I am sure you can translate:

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

I keep the head and the tail of the return list and modify the tail as I traverse the list argument.