Scheme list always in reverse order

Question

Probably a trivial question for most of the more advanced schemers here, but as a newcomer, I've found this to be a problem.

I need a way to construct a new list that is in the same order it was when it came in. As an example, say we are given a list '(1 2 0 3 4 0 0 5). But traversing the list and passing the cdr back as the 1st argument ends up constructing the new list backwards.

Here's an example in code:

I pass it an "old-list" that needs work done on it and an empty list as "new-list" to be formed and returned.

note that taking 0s out is just here as "some condition" that the new list must meet

  (define (form-new-list old-list new-list)
    (cond ((null? old-list) new-list)
          (else
           (if (eq? (car old-list) 0) (form-new-list (cdr old-list) new-list)
               (form-new-list (cdr old-list) (cons (car old-list) new-list))))))

  ;test
  (form-new-list '(1 2 0 3 4 0 0 5) '()) ; gives (5 4 3 2 1)
  ;but want (1 2 3 4 5)

I DO NOT just want to reverse the list that is returned with a reverse procedure, but rather, want the new list to be put together in the correct order in the first place.

Is there some kind of "trick" to this, like making the recursive call somewhere else perhaps?

Any advice is greatly appreciated.

Answer 1

You're looking for the natural way to traverse a list using recursion. Use this procedure as a template for your solution - it simply copies a list exactly as it is received:

(define (copy lst)
  (if (null? lst)
      '()
      (cons (car lst)
            (copy (cdr lst)))))

Notice the following points:

• The recursion ends when the input list is null, and given that we're building a new list, the correct value to return is the null list
• We're interested in building a new list, we do this by consing a new element for the output list, which in this case happens to be the first element of the input list (its car part)
• Finally, the recursive step advances by invoking the procedure with the rest of the input list (its cdr part)

As usual, I end up my answers to people learning how to think recursively by recommending you take a look at either The Little Schemer or How to Design Programs, both books will teach you how to grok recursive processes in general, using Scheme.