;; ex 2.5, pairs of integers. ;; Pair a, b can be stored as a single integer 2^a * 3^b, provided a ;; and b are both non-negative integers. The first part will be even, ;; the last odd. Getting rid of the even part will leave the odd, and ;; vice versa. ;; Helpers. (define (exp base n) (define (iter x result) ;; invariant: base^x * result is constant. (if (= 0 x) result (iter (- x 1) (* base result)))) (iter n 1)) (define (count-0-remainder-divisions n divisor) (define (iter try-exp) (if (= 0 (remainder n (exp divisor try-exp))) (iter (+ try-exp 1)) ;; Try another division. (- try-exp 1))) ;; We don't need to try 0 divisions, as that will obviously pass. (iter 1)) ;; cons, car, cdr (define (my-cons a b) (* (exp 2 a) (exp 3 b))) (define (my-car z) (count-0-remainder-divisions z 2)) (define (my-cdr z) (count-0-remainder-divisions z 3)) ;; Usage: (define test (my-cons 11 17)) (my-car test) (my-cdr test) ;; Another way to define count-0-remainder-divisions (define (divides? a b) (= 0 (remainder b a))) (define (count-0-remainder-divisions n divisor) (define (iter x divisions) (if (divides? divisor x) (iter (/ x divisor) (+ divisions 1)) divisions)) (iter n 0))

<< Previous exercise (2.4) | Index | Next exercise (2.6) >>

;; Constructor (define (cons a b) (* (expt 2 a) (expt 3 b))) ;; Enables us to calculate the log of n in base b (define (logb b n) (floor (/ (log n) (log b)))) ;; Selectors (define (car x) (logb 2 (/ x (gcd x (expt 3 (logb 3 x)))))) (define (cdr x) (logb 3 (/ x (gcd x (expt 2(logb 2 x))))))

This is probably similar to chekkal's answer at the end of the day. One downside is it returns floats, but this could probably be remedied via a round procedure (not yet introduced in course).

(define (cons a b) (* (expt 2 a) (expt 3 b))) ; once we factor out the 3s, then: ; 2^a = z ; log(2^a) = log(z) ; a*log(2) = log(z) ; a = log(z) / log (2) (define (car z) (define (divisble-by-3? a) (= (remainder a 3) 0)) (if (divisble-by-3? z) (car (/ z 3)) (/ (log z) (log 2)))) ; once we factor out the 2s, then: ; 3^b = z ; log(3^b) = log(z) ; b * log(3) = log(z) ; b = log(z) / log(3) (define (cdr z) (define (even? a) (= (remainder a 2) 0)) (if (even? z) (cdr (/ z 2)) (/ (log z) (log 3))))

I had originally tried using an invariant for count-0-remainder-divisions, but couldn't get it to work. Alas.