Question

我们也可以把集合看作是由它的 特征函数 定义：该函数读入一个数字，告诉我们这个数字是否是集合的一部分。在这种情况下，集合就是简单的 Int -> Bool 函数。（PLAI 一书中，第十二章中在研究环境的 子程序表示 时有提到。）

空集的特征函数是什么？总是返回假的函数。插入一个新元素所获得的集合呢？

(define empty (λ (n) #f))

(define (insert set val)
          (λ (n)
            (or (eq? n val)
                (contains? set n))))

(define (contains? set val)
  (set val))

由于集合由其特征函数表示， contains? 只需将该函数应用于该元素。请注意，客户程序还是完全不受干扰：

> (define x empty)
> (define y (insert x 3))
> (define z (insert y 5))
> (contains? z 2)
#f
> (contains? z 5)
#t

集合的子程序表示给我们带了了什么？灵活性！例如，我们可以定义所有偶数的集合：

(define even
  (λ (n) (even? n)))

我们前面考虑的任何 ADT 表示，都不能完整地表示这个集合。（为什么？）我们甚至可以定义非确定的集合：

(define random
  (λ (n) (> (random) 0.5)))

使用子程序表示，我们可以更自由地定义集合，此外它们同样可以与已有的集合操作交互！

> (define a (insert even 3))
> (define b (insert a 5))
> (contains? b 12)
#t
> (contains? b 5)
#t

相反，在上面我们看到的 ADT 表示中，不同的表示法之间不能互操作。列表实现集合的值不能被结构体实现的操作使用，反之亦然。ADT 从表示中抽象出来，但一次只允许 一种表示 。