How to implement append procedure using tail recursion in Scheme/Racket?

Question

For a long time I'm trying to implement the append procedure in Racket using tail recursion(iterative).

The best solution I did so far is this:

(define (my-reverse lst)
  (define (iter lst reversed)
    (if (null? lst)
        reversed
        (iter (cdr lst) (cons (car lst) reversed))))
  (iter lst '()))

(define (append-iter el lst)
  (my-reverse (cons el (my-reverse lst))))

(append-iter 4 '(1 2 3)) ; (1 2 3 4)

My question is whether there is a better a way of implementation?

Funny how Oscar and Will seem to have forgotten they wrote answers for the same question 8 years ago — Sylwester, Nov 16 '20 at 23:24
links, please. :) ah, the dup. thanks! it'll be funniest if the answers are also the same now as they were back then... @Sylwester — Will Ness, Nov 16 '20 at 23:28
@Sylwester ah yes, I remember that one. it had one more requirement for the solution though, to be "functional". this one I took as more of a request for commentary for the OP's code in the question, how it can be improved. so I guess I'd recommend my answer on the dup as "better way". :) — Will Ness, Nov 16 '20 at 23:34

Óscar López · Accepted Answer · 2020-11-14T15:32:11.727

Well, it depends on your definition of "better" :) . Your solution is simple, and you won't find a more straightforward way to write your own procedure to append an element at the end of a list, using tail recursion.

My only comment is that my-reverse is doing the same as the built-in reverse procedure, which most certainly will be tail recursive, so you can simply write it as:

(define (append-iter el lst)
  (reverse (cons el (reverse lst))))

If you're ok with using continuation passing style, the following solution is also tail-recursive and it only depends on the most basic primitive procedures:

(define (append-iter el lst)
  (append-cps lst (cons el '()) (lambda (x) x)))

(define (append-cps lst1 lst2 k)
  (if (null? lst1)
      (k lst2)
      (append-cps
       (cdr lst1)
       lst2
       (lambda (appended-cdr)
         (k (cons (car lst1) appended-cdr))))))

Either way, it works as expected:

(append-iter 4 '(1 2 3))
=> '(1 2 3 4)

If you're curious, the CPS solution will evaluate to an expression like the one shown below, which naturally leads to the answer:

((lambda (append-cdr)
   ((lambda (appended-cdr)
      ((lambda (appended-cdr)
         ((lambda (x) x)
          (cons 1 appended-cdr)))
       (cons 2 appended-cdr)))
    (cons 3 append-cdr)))
 '(4))
=> '(1 2 3 4)

score 1 · Answer 2 · answered Nov 14 '20 at 16:51

Yes,

(define (rev-append lst reversed)
    (if (null? lst)
        reversed
        (rev-append (cdr lst) 
                    (cons (car lst) reversed))))

(define (append-iter el lst)
  (rev-append (rev-append lst '()) 
              (cons el '())))

is marginally "better".

rev-append is your my-reverse's iter. It deserves its own top level binding.

How to implement append procedure using tail recursion in Scheme/Racket?

2 Answers2