sicp-ex-2.20


 (define (same-parity first . rest) 
   (define (same-parity-iter source dist remainder-val) 
     (if (null? source) 
         dist 
         (same-parity-iter (cdr source) 
                           (if (= (remainder (car source) 2) remainder-val) 
                               (append dist (list (car source))) 
                               dist) 
                           remainder-val))) 
    
   (same-parity-iter rest (list first) (remainder first 2))) 

mueen

Using append as above is expensive, as it will iterate through all the elements of the list you build, at _each_ iteration.

It's better simply to build the list in reverse order, and then reverse the final list at the end


 (define (same-parity first . rest) 
   (let ((yes? (if (even? first) 
                   even? 
                   odd?))) 
     (define (iter items result) 
       (if (null? items) 
           (reverse result) 
           (iter (cdr items) (if (yes? (car items)) 
                                 (cons (car items) result) 
                                 result)))) 
     (iter rest (list first)))) 

 (define (sam-parity first . rest) 
   (define (inter yes? lat) 
     (cond 
       ((null? lat) (quote())) 
       ((yes? (car lat))(cons (car lat) (inter yes? (cdr lat)))) 
       (else 
        (inter yes? (cdr lat))))) 
   (if (odd? first) 
       (inter odd? rest) 
       (inter even? rest)))  

<< Previous exercise (2.19) | Index | Next exercise (2.21) >>


jz

  
 ;; ex 2.20, dotted-tail notation. 
  
 (define (same-parity first . rest) 
   (define (congruent-to-first-mod-2? a) 
     (= (remainder a 2) (remainder first 2))) 
  
   (define (select-same-parity items) 
     (if (null? items)  
         items 
         (let ((curr (car items)) 
               (select-rest (select-same-parity (cdr items)))) 
           (if (congruent-to-first-mod-2? curr) 
               (cons curr select-rest) 
               select-rest)))) 
  
   (cons first (select-same-parity rest))) 
  
 ;; an alternative implementation by andras: 
 (define (same-parity a . l) 
         (define (sp-builder result tail) 
         (if (null? tail) 
         result 
         (if (even? (+ a (car tail))) 
         ;;test for same parity 
         ;;if the current beginning of the rest (car tail) is the same parity as "a", then it is appended to the result, else the result is left untouched 
         (sp-builder (append result (list (car tail))) (cdr tail)) 
         (sp-builder result (cdr tail))))) 
         (sp-builder (list a) l)) 
  
 ;; Usage: 
 (same-parity 1 2 3 4 5 6 7) 
 ;; (1 3 5 7) 
  
 (same-parity 2 3 4 5 6 7 8) 
 ;; (2 4 6 8) 
  


chris

This does it by passing the relevant test:

 (define (same-parity . l) 
   (define (parity l test) 
     (if (null? l) 
         (list) 
         (if (test (car l)) 
             (cons (car l)(parity (cdr l) test)) 
             (parity (cdr l) test)))) 
    
   (if (even? (car l)) 
       (parity l even?) 
       (parity l odd?))) 

erik

  
  
 (define (same-parity n . lst) 
    (define same-parity? (if (even? n) even? odd?)) 
    (define (iter lst acc) 
      (if (null? lst) 
          acc 
          (let ((first (car lst)) 
                (rest (cdr lst))) 
            (iter rest 
                  (if (same-parity? first) 
                      (cons first acc) 
                      acc))))) 
    (cons n (reverse (iter lst null)))) 

The footnote for this section shows a funny lambda:

  (define f (lambda (x y . z) z))
  (f 1 2 3 4 5)
  => (3 4 5)

Defining a lambda that takes a variable number of args is isn't done in the obvious way:

  (define h (lambda (. w) w))
  ;Ill-formed dotted list: (. w) ... etc, lots of errors.

This has to be defined like this:

  (define h (lambda w w))
  (h 1 2 3 4)
  => (1 2 3 4)

Shubhro

 (define (same-parity x . y) 
   (define (parity list rem) 
     (cond ((null? list) list) 
           ((= rem (remainder (car list) 2)) 
            (cons (car list) (parity (cdr list) rem) )) 
           (else 
            (parity (cdr list) rem)))) 
   (if (even? x) 
       (parity y 0) 
       (parity y 1))) 

Daniel-Amariei

Recursive process

 (define (same-parity . L) 
   (define (filter x) 
     (if (even? x) 
         even? 
         odd?)) 
   (define (construct f L) 
     (cond ((null? L) '()) 
           ((f (car L)) (cons (car L)  
                                     (construct f (cdr L)))) 
           (else (construct f (cdr L))))) 
   (construct (filter (car L)) L)) 
  
 (same-parity 2 3 4 5 6 7) ;; '(2 4 6)