Scheme - Using cons properly to create lists

Question

I've been trying to solve exercise 2.20 of SICP, where "dotted-tail" notation is introduced. My problem is that, instead of returning a proper list with results, my function returns a nested list. I know that there is something wrong with the way I'm calling cons, but I still have no clue of how to solve the issue.

So here is my function:

(define (same-parity first . items)

  (define (speccar items)
    (cond ((null? items) 2) 
          ((not (pair? items)) (modulo items 2))
          (else (modulo (car items) 2))))

  (define (iter-parity first items result)
    (let ((parityFirst (modulo first 2)) (samepar (speccar items)))
      (if (null? items)
          result
          (if (= parityFirst samepar)
              ;; This next line is where the problem is...
              (iter-parity first (cdr items) (cons (list result) (list (car items))))
              (iter-parity first (cdr items) result)))))

  (iter-parity first items first))

Test:

(same-parity 1 2 3 4 5)
((((1) 3)) 5)

Now, I've read the following answers that deal with a similar problem:

Cons element to list vs cons list to element in Scheme

How to use 'cons' without generating nested lists in Scheme?

They certainly make it clear where the problem is coming from, but how does one go about to actually implement a proper solution? And, if possible, what is the correct way of "thinking" in Scheme to avoid these traps/pitfalls?

Answer 1

You're incorrectly building the output list - remember: the first argument to cons should be the current element and the second argument, the result list.

Also, given that you're using tail recursion, you'll have to reverse the output at the end to preserve the same order as in the original list. Try this:

(define (same-parity first . items)
  (define (speccar items)
    (cond ((null? items) 2) 
          ((not (pair? items)) (modulo items 2))
          (else (modulo (car items) 2))))
  (define (iter-parity first items result)
    (let ((parityFirst (modulo first 2))
          (samepar (speccar items)))
      (if (null? items)
          (reverse result)
          (if (= parityFirst samepar)
              (iter-parity first
                           (cdr items)
                           (cons (car items) result))
              (iter-parity first
                           (cdr items)
                           result)))))  
  (iter-parity first items (list first)))

The above solution can be greatly simplified if we use built-in procedures (don't reinvent the wheel!). This is the recommended way to write programs in Scheme - adhering to a functional style:

(define (same-parity head . tail)
  (if (even? head)
      (filter even? (cons head tail))
      (filter  odd? (cons head tail))))

Either way, it works as expected:

(same-parity 1 2 3 4 5)
=> '(1 3 5)