练习 3.17

在书本 177 页的脚注中提到,可以使用 eq? 判断对象的唯一性:

1 ]=> (define x (cons 1 2))

;Value: x

1 ]=> (eq? x x)

;Value: #t

1 ]=> (eq? x (cons 1 2))

;Value: #f

利用 eq? 的这个特性,我们可以通过维持一个记录列表,然后遍历给定的序对结构,每当遇到一个序对时,判断它是否已经存在于记录列表,如果不存在就将它加进记录列表,并继续遍历这个序对的 carcdr 部分,当给定的序对结构遍历完之后,记录列表的长度就是序对的真正个数。

以下是相应的过程定义:

;;; 17-count-pairs.scm

(define (count-pairs x)
    (length (inner x '())))

(define (inner x memo-list)
    (if (and (pair? x)
             (false? (memq x memo-list)))
        (inner (car x)
               (inner (cdr x)
                      (cons x memo-list)))
        memo-list))

inner 的定义中使用了内置函数 memq ,用于检查给定序对是否存在于记录列表内。

测试:

1 ]=> (load "17-count-pairs.scm")

;Loading "17-count-pairs.scm"... done
;Value: inner

1 ]=> (count-pairs (cons (cons 1 2) (cons 3 4)))

;Value: 3

1 ]=> (count-pairs (list 1 2 3))

;Value: 3

1 ]=> (count-pairs (let ((x (cons 1 2)))    ; 带有重复指针的序对
                     (cons x x)))

;Value: 2

讨论

blog comments powered by Disqus