Schema - Correct Use of Cons to Create Lists
I was trying to solve Exercise 2.20 from SICP, which introduces the dotted tail notation. My problem is that instead of returning the correct list with the results, my function returns a nested list. I know there is something wrong with what I call the cons, but I still don't know how to solve the problem.
So here's 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)
I have now read the following answers that address a similar problem:
Cons element to display a list vs cons for an element in a schema
How can I use "cons" without generating nested lists in Schema?
They definitely make it clear where the problem is coming from, but how to do it to actually implement the correct solution? And, if possible, what is the correct way to "think" in the Outline to avoid these pitfalls / pitfalls?
source to share
You are creating the output list incorrectly - remember: the first argument cons
must be the current item and the second must be the list of results.
Also, given that you are using tail recursion, you will have reverse
to output at the end to keep the same order as in the original list. Try the following:
(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 inline routines (don't reinvent the wheel!). This is the recommended way to write Scheme programs - in a functional style:
(define (same-parity head . tail)
(if (even? head)
(filter even? (cons head tail))
(filter odd? (cons head tail))))
Anyway, it works as expected:
(same-parity 1 2 3 4 5)
=> '(1 3 5)
source to share