我目前正在阅读SICP，并在练习2.5:
2.5。证明如果将a和b表示为整数2a3b，则可以只用数字和算术运算来表示非负整数对。给出程序
cons、car、cdr的相应定义。
我发现了一个代码:
(define (my-cons a b)
(* (expt 2 a) (expt 3 b)))
(define (my-car x)
(define (car-iter x count)
(if (= 0 (remainder x 2))
(car-iter (/ x 2) (+ 1 count))
count))
(car-iter x 0))
(define (my-cdr x)
(define (cdr-iter x count)
(if (= 0 (remainder x 3))
(cdr-iter (/ x 3) (+ 1 count))
count))
(cdr-iter x 0))
我的问题是:如果要求"非负整数"怎么办?
?的例子:
> (define x (my-cons 2 -5))
> (my-car x)
2
> (my-cdr x)
-5
如何修改代码?我想不明白。
谢谢。祝你过得愉快。
正如amalloy在评论中所说，这实际上是一个数学问题。这种编码之所以有效，是因为算术基本定理，即任何正自然数都有一个唯一的质因数分解:每个正自然数都可以被唯一地表示为若干素数的幂的乘积，其中1是0素数的乘积。
所以你可以使用一个或多个额外的素数因子来编码整数的符号(事实上，你只需要一个，比如你可以把它写成2^a3^b5^s，其中s是[0,3]中的整数，它编码了两个元素的符号)
另一种方法是简单地使用现有的表示，但将整数映射到自然数。这很好，因为它是一个实际的证明，没有比自然数更多的整数。这样的映射可能是:
- 如果i>= 0则2i.
- 否则-2i - 1.
很容易看出这是一个一对一的对应关系，并且0映射到0(这使得0对nil来说是一个很好的值)。
这里是这些地图，写(对不起)在类型球拍，因为我试图找出如果我可以使用它。
(define (Z->N (i : Integer)) : Natural
;; map an integer to a natural
(if (>= i 0)
(* i 2)
(- (* (- i) 2) 1)))
(define (N->Z (n : Natural)) : Integer
;; map the naturals into the integers
(let-values ([(q r) (quotient/remainder n 2)])
(if (zero? r)
q
(- (- q) 1))))
现在有另一个问题与你的实现:它将愉快地处理形式不是2^a3^b的数字，例如任何有其他质因数的数字。处理这个问题的方法是在提取幂时检查数字是否符合这种形式:在实践中，这意味着检查数字是否符合2^a*3^b*1的形式。
所以下面的代码做了这个，并且像上面一样编码整数。这也是在类型化的球拍中(抱歉，再次)，它还使用了多个值和可能只存在于球拍中的其他一些东西。
(define (defactor (n : Natural) (p : Natural)) : (Values Natural Natural)
;; Given n and a factor p, return m where p does not divide m,
;; and j, the number of factors of p removed (so n = m*p^j)
(let df-loop ([m : Natural n]
[j : Natural 0])
(let-values ([(q r) (quotient/remainder m p)])
(if (zero? r)
(df-loop q (+ j 1))
(values m j)))))
(define (kar&kdr (k : Positive-Integer)) : (Values Integer Integer)
;; Given something which should be a kons, return its kar & kdr.
;; If it is not a kons signal an error
(let*-values ([(k2 encoded-kar) (defactor k 2)]
[(k23 encoded-kdr) (defactor k2 3)])
(unless (= k23 1)
(error 'kar&kdr "not a cons"))
(values (N->Z encoded-kar) (N->Z encoded-kdr))))
(define (kons (the-kar : Integer) (the-kdr : Integer)) : Positive-Integer
(* (expt 2 (Z->N the-kar))
(expt 3 (Z->N the-kdr))))
(define (kar (the-kons : Positive-Integer)) : Integer
(let-values ([(the-kar the-kdr) (kar&kdr the-kons)])
the-kar))
(define (kdr (the-kons : Positive-Integer)) : Integer
(let-values ([(the-kar the-kdr) (kar&kdr the-kons)])
the-kdr))
我们可以更进一步，定义一个空列表的表示形式，它将是0和一种制作列表的方式:
;;; since 2^a3^b is never zero, 0 is a good candidate for the empty
;;; list: 'kill' is a pun on 'nil'.
;;;
(define kill : Zero 0)
;;; And now we can write some predicates and a version of list.
;;; (kist 1 2 3) takes a very, very long time.
;;;
(define (kill? (x : Natural)) : Boolean
(zero? x))
(define (kons? (x : Natural)) : Boolean
(not (kill? x)))
(define (kist . (l : Integer *)) : Natural
(let kist/spread ((lt l))
(if (null? lt)
kill
(kons (first lt) (kist/spread (rest lt))))))
现在和
> (define d (kons 123 -456))
> d
- : Integer [more precisely: Nonnegative-Integer]
51385665200410193914365219310409629004573395973849642473134969706165383608831740620563388986738635202925909198851954060195023302783671526117732269828652603388431987979605951272414330987611274752111186624164906143978901704325355283206259678088536996807776750955110998323447711166379786727609752016045005681785186498933895920793982869940159108073471074955985333560653268614500306816876936016985137986665262182684386364851688838680773491949813254691225004097103180392486216812280763694296818736638062547181764608
> (kar d)
- : Integer
123
> (kdr d)
- : Integer
-456
> (kdr (+ d 1))
kar&kdr: not a cons [,bt for context]
如果你尝试计算，比如(kist 1 2 3)，它将花费非常非常长的时间。