Exercise 2.20 introduces Scheme's dotted-tail notation, which allows procedures like
+, *, and list to take arbitrary numbers of arguments. This is known as a variadic function and is supported in many programming languages with different syntax. In Scheme, a parameter list that has a dot before the last parameter name indicates that when the procedure is called, the initial parameters will be treated as normal, but the final parameter's value will be a list of any remaining arguments.The following examples are given:
(define (f x y . z) <body>)
(define (g . w) <body>)
The procedure
f can be called with two or more arguments. The body of the f procedure will refer to its first two parameters as x and y, and any remaining parameters passed to the procedure will be accessible through the list named z. The procedure g can be called with zero or more parameters. Any parameters will be in the list w.This exercise asks us to use dotted-tail notation to write a procedure
same-parity that takes one or more integer parameters and returns a list of all the arguments that have the same even-odd parity as the first argument. For example:(same-parity 1 2 3 4 5 6 7)
(1 3 5 7)
(same-parity 2 3 4 5 6 7)
(2 4 6)
We'll design a solution that uses an iterative helper procedure similar to the second
length example given in section 2.2.1. The helper function will take as its parameters the list of items to iterate through and a variable to store the answer in as we iterate.(define (same-parity a . z)
(define (iter items answer)
(if (null? items)
answer
(iter (cdr items)
(if (= (remainder (car items) 2)
(remainder a 2))
(append answer (list (car items)))
answer))))
(iter z (list a)))
The
same-parity procedure takes a first parameter a, and any remaining parameters are accessed through the list z. Processing the list is delegated to the helper procedure iter. The first thing iter does is check the list to see if it's null. If so we just return the answer. If there are items left to process in the list, iter is called again with the cdr of the list as its first parameter and the answer as its second parameter. If the car of the list has the same even-odd parity as the first argument to same-parity, then it's appended to the answer.> (same-parity 1 2 3 4 5 6 7)
(1 3 5 7)
> (same-parity 2 3 4 5 6 7)
(2 4 6)
Related:
For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.
5 comments:
Here is a version. Question to you bill is my version "better" because its easier to read? Or in general is it better to have more succinct code?
(define (same-parity a . z)
(cond ((null? z) a)
((even? a) (cons a (all-even z)))
(else (cons a (all-odd z)))))
(define (all-odd lst)
(define (iter x)
(cond ((null? x) nil)
((odd? (car x))
(cons (car x) (iter (cdr x))))
(else (iter (cdr x)))))
(iter lst))
(define (all-even lst)
(define (iter x result)
(cond ((null? x) (reverse result))
((even? (car x)) (iter (cdr x) (cons (car x) result)))
(else (iter (cdr x) result))))
(iter lst nil))
(define (find condition l)
(if (null? l)
(list)
(if (condition (car l))
(cons (car l) (find condition (cdr l)))
(find condition (cdr l)))))
(define (same-parity x . y)
(if (even? x)
(cons x (find even? y))
(cons x (find odd? y))
))
Here's my version:
"Some overly-commented mess down below
Gives the order in reverse order :-) too lazy to change that"
(define (same_parity x . y)
"Checks the parity of a given number.
If a number is odd, the procedure evaluates to 3
If a number is even, the procedure evaluates to 2"
(define (parity_of x)
(if (even? x) 2 3))
"The output produced by this procedure is made of a number value representing the citizen and an id indicating whether or not he's good or bad.
0 = bad, 1 = good. To be good, citizen must have to have the same parity as the argument parity_of_x"
(define (profiling unprofiled_citizen)
(if (= (parity_of unprofiled_citizen) (parity_of x))
(cons unprofiled_citizen 1)
(cons unprofiled_citizen 0)))
"Profiled citizen's value"
(define (citizen_value profiled_citizen)
(car profiled_citizen))
"Profiled citizen's id"
(define (citizen_id profiled_citizen)
(cdr profiled_citizen))
"We live in a police state ! The citizens with an id of 0 are not allowed
Those with an id of 1 are accepted in town."
(define (good_or_bad_citizen? citizen result)
(if (= (citizen_id citizen) 0)
result
(cons (citizen_value citizen) result)))
(define (one_of_many unprofiled_citizens)
(car unprofiled_citizens))
(define (the_rest_of unprofiled_citizens)
(cdr unprofiled_citizens))
(define (filter result unprofiled_citizens)
(if (null? unprofiled_citizens)
result
(filter (good_or_bad_citizen? (profiling (one_of_many unprofiled_citizens)) result)
(the_rest_of unprofiled_citizens))))
(filter '() y))
Here is a recursive version:
(define (same-parity x . t)
(let ((parity (remainder x 2)))
(define (go l)
(cond ((null? l) ())
((= (remainder (car l) 2) parity) (cons (car l) (go (cdr l))))
(else (go (cdr l)))))
(go (cons x t))))
My (less polished) version:
;miscellaneous procedure
(define (xor p q)
(and (or p q)
(not (and p q))))
;same-parity procedure: accepts a an arbitrary number of integer arguments
;and returns as a list those that match the parity of the first
(define (same-parity x . y)
(define (even? n)
(= (remainder n 2) 0))
(define (diff-parity? a b)
(xor (even? a) (even? b)))
(define (iter y result)
(cond ((null? y) (append (list x) result))
((diff-parity? x (car y)) (iter (cdr y) result))
(else (iter (cdr y) (append result (list (car y)))))))
(iter y (list)))
I really appreciate being able to follow along with your solutions. Thanks!
Post a Comment