I was experimenting with reversing a list in Scheme. I came up with this code:
(define (rev lst)
(let loop ((lst lst) (result '()))
(if (null? lst)
result
(loop (cdr lst) (cons (car lst) result)))))
It works fine, but I wanted to see (as an experiment) if I can rewrite this as non-TCO, since Non TCO are usually simpler to write.
I did a dump rearrangement to get rid of the accumulator:
(define (rev lst)
(if (null? lst)
'()
(cons (car lst) (rev (cdr lst)))))
But this one just copy the list, is there an easy way to create non TCO recursive function that reverse a list?
I was asking ChatGPT, and he shows me the code that use append that was correct. But can you do this without append that will traverse the list?
This may be a silly question, but I have no idea if it's possible, that's why I'm asking.
While writing this question, I came up with a more fundamental one. Does TCO algorithm with an accumulator always create list in reverse and non-TCO always in same order? Or maybe you can create an algorithm that break this rule. So far, I always use (revese result) when operating on lists when using accumulator.
There's a Python implementation here and this is a translation to Scheme:
(define (rev lst)
(if (or (null? lst) (null? (cdr lst)))
lst
(let ((new-lst (rev (cdr lst))))
(set-cdr! (cdr lst) lst)
(set-cdr! lst '())
new-lst)))