sicp-ex-2.20



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


 (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)))  

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) 

wind2412

My solution.

  (define (same-parity x . w) 
     (define (get-all w r) 
       (if (null? w) `() 
           (if (= (remainder (car w) 2) r) (cons (car w) (get-all (cdr w) r)) 
               (get-all (cdr w) r)))) 
     (cons x (get-all w (remainder x 2)))) 

It is possible to test for parity using just the sum of two terms (odd+odd=pair pair+pair=pair). Bellow Using the sum of first and each new term.

 (define (same-parity first . l)    
     (define (iter lista lfinal) 
         (if (null? lista)  
             lfinal 
             (if (even? (+ first (car lista))) 
                 (iter (cdr lista) (append lfinal (list (car lista)))) 
                 (iter (cdr lista) lfinal)))) 
     (iter l (list first))) 

acml

My recursive solution.


 (define (same-parity x . y) 
   (define (search-parity a r) 
     (if (null? r) 
         '() 
       (if (= (remainder a 2) (remainder (car r) 2)) 
           (cons (car r) (search-parity a (cdr r))) 
         (search-parity a (cdr r))))) 
   (cons x (search-parity x y)))