SICP 問題 2.5（consの別表現その２）

【問題】

a と b の対を積 2^a・3^b とである整数で表現するなら、非負の整数の対は数と算術演算だけを使って表現できることを表せ。
これに対応する手続き cons、car、及び cdr の定義は何か。

【解答】

素数だからこの表現が可能になるのか？
直感的にはすぐ理解できるんだけど、「表せ」って言われると困るなぁ。どうすればいいんだろ。

先に cons、car、cdr の定義からいくか。
実験したいけど、既存のこいつらを上書きしたくないので、prefixとして "my-"をつけよう。

(define (my-cons x y)
  (* (expt 2 x) (expt 3 y)))

(define (my-car v)
  (my-selector v 2 3 0 0))

(define (my-cdr v)
  (my-selector v 3 2 0 0))

(define (my-selector v base_a base_b a b)
  (cond ((= (modulo v base_a) 0)
	 (my-selector (quotient v base_a) base_a base_b (+ 1 a) b))
	((= (modulo v base_b) 0)
	 (my-selector (quotient v base_b) base_a base_b a (+ 1 b)))
	((= v 1)
	 a)
	(else
	 #f)))

これでいくはず。受け取った整数に、2、3 以外の素数が因数に入っていた場合は #f を返す。
では実験。

gosh> (define v_2_3 (my-cons 2 3))

v_2_3

gosh> v_2_3

108

gosh> (my-car v_2_3)

2

gosh> (my-cdr v_2_3)

3

gosh> (define v_3_7 (my-cons 3 7))

v_3_7

gosh> v_3_7

17496

gosh> (my-car v_3_7)

3

gosh> (my-cdr v_3_7)

7

gosh> (my-car 540)

#f

gosh> 

うん、OKっぽい。最後の540は、v_2_3 に、5（対象外の因数）を掛けたもの。
ちゃんと #f が返ってきて、正しくない対であることが分かる。