SICP - exercise 2.20 - same-parity

Question

Exercise 2.20.  
The procedures +, *, and list take arbitrary numbers of arguments. One way to define such procedures is to use define with dotted-tail notation. In a procedure definition, a parameter list that has a dot before the last parameter name indicates that, when the procedure is called, the initial parameters (if any) will have as values the initial arguments, as usual, but the final parameter's value will be a list of any remaining arguments. For instance, given the definition

(define (f x y . z) )

the procedure f can be called with two or more arguments. If we evaluate

(f 1 2 3 4 5 6)

then in the body of f, x will be 1, y will be 2, and z will be the list (3 4 5 6). Given the definition

(define (g . w) )

the procedure g can be called with zero or more arguments. If we evaluate

(g 1 2 3 4 5 6)

then in the body of g, w will be the list (1 2 3 4 5 6).

Use this notation to write a procedure same-parity that takes one or more integers 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)

source

Please review my code.

I have implemented a helper procedure, called predmap (Note: I am not aware of (filter) before writing this exercise). It's identical to map, but the function argument is a predicate. The item will be added in the new list if the predicate is true.

(define (predmap pred lst)
    (if (null? lst) '()
        (let ((carst (car lst))
            (next (predmap pred (cdr lst))))
            (if (pred carst)
                (cons carst next)
                next))))

Here is the same-parity procedure:

(define (same-parity . lst)
    (if (null? lst) '()
        (cons
            (car lst)
            (predmap (if (even? (car lst)) even? (lambda (x) (not (even? x))))
            (cdr lst)))))

In the second argument to cons, I put the if statement in the function argument directly to avoid repeating the call to predmap in the code. But it seems to look complicated now.

How can I make this code better and faster? Is there a better solution? Perhaps one where we would not need procedures like predmap?

Answer 1

A simple way to determine the parity of a whole number is calculate the modulus of the number wrt 2:

(modulo 4 2) => 0 (even)
(modulo 5 2) => 1 (odd)

Your predmap is useful however it's a reinvention of a wheel. The standard function filter does the same thing.

So you could write the solution as:

(define (same-parity xs)
  (let ((parity (modulo (car xs) 2)))
    (cons (car xs) 
          (filter (lambda (x) (= (modulo x 2) parity))
                  (cdr xs)))))

Answer 2

Disclaimer: my Lisp is extremely rusty.

• same-parity must have at least one argument, so the proper declaration would be (same-parity arg . rest).

• A more natural predicate for determining same parity of x,y is (even? (- x y))

• A more natural helper is (same-parity-helper arg lst). Notice the absence of dot: it can recurse.

• Putting it all together,

      (define (same-parity-helper arg lst)
          (if (null? lst) '()
              (cons
                  (if (even? (- arg (car lst))
                      (car lst))
                      '())
                  (same-parity-helper arg (cdr lst)))))
  
      (define (same-parity arg . rest)
          (same-parity-helper arg rest))