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