<< 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)))
;; 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)
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?)))
(define (same-parity x . y)
;; Finds the list of elements in y with same parity as x
(define (same-parity-rest y)
(cond
(
(null? y) '()
)
(
(parity-2 (car y) x)
(cons (car y) (same-parity-rest (cdr y)) )
)
(
else ;;(car y) has different parity than x..
(same-parity-rest (cdr y))
)
)
)
;; Check if 2 integers have same parity
(define (parity-2 a b)
(= (remainder (+ a b) 2) 0) ;; is thier sum even ?
)
;; Combine the result
(cons x (same-parity-rest y))
)
(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)
This is shown in R5RS https://groups.csail.mit.edu/mac/ftpdir/scheme-reports/r5rs-html/r5rs_6.html#IDX89
(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)))
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)
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)))
(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)))
(define (find-numbers items condition) (if (null? items) (list) (if (condition (car items)) (cons (car items) (find-numbers (cdr items) condition)) (find-numbers (cdr items) condition)))) (define (same-parity first . items) (if (odd? first) (find-numbers items odd?) (find-numbers items even?)))
Here is my solution
(define (same-parity first . items)
(define (iter items)
(if (null? items)
'()
(if (even? (+ (car items) first))
(cons (car items) (iter (cdr items)))
(iter (cdr items)))))
(cons first (iter items)))
Evan
(define (same-parity . l)
(define (first-parity)
(if (even? (car l))
even?
odd?))
(filter (first-parity) l))
(define (same-parity fst . rest)
(let ((pred (if (even? fst) even? odd?)))
(filter pred (cons fst rest))))
(define (same-parity i . l)
(define (same-parity-i x)
(if (even? (+ i x)) #t #f))
(cond ((null? l) i)
((same-parity-i (car l))
(cons i (apply same-parity l)))
(else (apply same-parity i (cdr l)))))
This solution leverages abstraction, by introducing a `sub-list` procedure that returns a subset of the input that matches a predicate. `same-parity` is defined in terms of `sub-list`.
(define (sub-list predicate? x) (define (sub-list-iter items result) (if (null? items) (reverse result) (let ((caritems (car items))) (cond ((predicate? caritems) (sub-list-iter (cdr items) (cons caritems result))) (else (sub-list-iter (cdr items) result)))))) (sub-list-iter x nil)) (define (same-parity x . A) (if (even? x) (sub-list even? A) (sub-list odd? A)))
(define (same-parity x . y)
(define (filter p items)
(cond ((null? items) #nil)
((p (car items)) (cons (car items) (filter p (cdr items))))
(else (filter p (cdr items)))))
(let ((parity (remainder x 2)))
(cons x (filter (lambda (x) (= parity (remainder x 2))) y))))
It's surprising how many of the above solutions use functions that have not been introduced in the book at this point. Here's my solution:
(define (same-parity . args)
(define (same-parity-step parity lst)
(cond ((null? lst) NIL)
((= parity (remainder (car lst) 2)) (cons (car lst) (same-parity-step parity (cdr lst))))
(else (same-parity-step parity (cdr lst)))
)
)
(same-parity-step (remainder (car args) 2) args)
)
(define (same-parity a . b)
(define (iter b result)
(cond ((null? b)
(reverse result))
((or (and (even? a) (even? (car b)))
(and (odd? a) (odd? (car b))))
(iter (cdr b) (cons (car b) result)))
(else
(iter (cdr b) result))))
(iter b (list a)))
Or non-iteratively.
(define (same-parity a . b)
(define (aux b)
(cond ((null? b)
b)
((or (and (even? a) (even? (car b)))
(and (odd? a) (odd? (car b))))
(cons (car b) (aux (cdr b))))
(else
(aux (cdr b)))))
(cons a (aux b)))
(define (same-parity a . list)
(define (reverse list)
(define (iter source result)
(if (null? source)
result
(iter (cdr source) (cons (car source) result))))
(iter list ()))
(define (construct test source result)
(if (null? source)
(reverse result)
(if (test (car source))
(construct test (cdr source) (cons (car source) result))
(construct test (cdr source) result))))
(cons a (construct
(if (even? a) even? odd?)
list
'())))
(define (same-parity a . b)
(letrec ((sp-rec (lambda (a c d)
(if (not (null? c))
(if (= (modulo a 2) 0)
(if (= (modulo (car c) 2) 0) ; (modulo a 2) equals 0
(sp-rec a (cdr c) (cons (car c) d))
(sp-rec a (cdr c) d))
(if (= (modulo (car c) 2) 1) ; (modulo a 2) equals 1
(sp-rec a (cdr c) (cons (car c) d))
(sp-rec a (cdr c) d)))
d)))
(reverse (lambda (l)
(letrec ((rev-rec (lambda (a b)
(if (null? a)
b
(rev-rec (cdr a) (cons (car a) b))))))
(rev-rec l (list))))))
(cons a (reverse (sp-rec a b (list))))))
My solution.
(define (same-parity . l) (define (helper items flag) (cond ((null? items) nil) ((= (remainder (car items) 2) flag) (cons (car items) (helper (cdr items) flag))) (else (helper (cdr items) flag)))) (cons (car l) (helper (cdr l) (remainder (car l) 2)))) (same-parity 1 2 3 4 5 6 7) (newline) (same-parity 2 3 4 5 6 7)
Summary of history comments:
jz's dotted-tail notation ("implementation by andras" uses one different method to test parity based on sum remainder), chris's (uses one different interface), erik's (use let), Shubhro's (one different method to test parity based on remainder), Daniel-Amariei's, ly's, Marisa's, joshroybal's (iter same as mueen's and non-iteratively same as jz's), yc's share the same basic idea as mueen's solution.
---
The method to test parity is same as "implementation by andras": pritesh's, Evan's, thongpv87's (uses apply).
The method to test parity is same as Shubhro's: wind2412's, acml's, 2bdkid's (#nil depends on the interpreter.), Shun's (uses letrec and a bit unnecessarily complexer), Birdy's.
All the above share the same basic idea as mueen's solution.
---
depaulagu's uses the internal filter. stewoe's is based on depaulagu's and same.
---
I didn't check the detailed implementation of reverse above.
(define (same-parity x . r)
(define (parity x)
(if (even? x) 'even 'odd))
(define (s-p x r)
(let ((r (if (list? (car r)) (car r) r)))
(cond ((null? r) (list x))
(else (if (equal? (parity x) (parity (car r)))
(append (same-parity x (cdr r)) (list (car r)))
(same-parity x (cdr r)))))))
(let ((result (s-p x r)))
(cons (car result) (reverse (cdr result)))))
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))))jz
(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)))