Working backwards through a list in scheme

Question

I'm trying to figure out how to work through a list in reverse order (back to front) in Scheme using recursion. My research shows that there is a reverse function that you can use on a list but I would not like to go that route.

I know that the following returns the last element in a list;

(caddr '(1 5 3))
returns 3

I would like to be able to send the remaining 1 5 back through the function, look at the last element again and repeat until the list is exhausted

From left to right is simple enough, you look at the car of the list and send back the cdr.

Break down the problem in the base step, the recursive step and what order they go in. Hint: If you first do the recursive step, then the base, you'd recurse through the entire list and then handle the base case, and then do the remaining elements as the stack unwinds. — yan
The function caddr does not return the last element in 'a list'; it returns the last element in 'your list'. — GoZoner

uselpa uselpa · Accepted Answer · 2014-02-10T17:48:41

Do the recursive call first, then the processing of the car. Example:

(define (process-in-reverse lst fun)
  (when (not (null? lst))
    (process-in-reverse (cdr lst) fun)
    (fun (car lst))))

then

> (process-in-reverse '(1 5 3) display)
351

If you just want to reverse the result and if subsequent calls are independent of previous calls, an accumulator will do and is tail-recursive:

(define (process-reverse-result lst fun)
  (let loop ((lst lst) (res null))
    (if (null? lst)
        res
        (loop (cdr lst) 
              (cons (fun (car lst)) res)))))

then

> (process-reverse-result '(1 5 3) add1)
'(4 6 2)

Working backwards through a list in scheme

1 Answers