Question

我们先来讨论抽象数据类型（ADT）。ADT 是隐藏其表示、只提供对值的操作的数据类型。

例如， 整数的集合 ADT 可以定义如下：

adt Set 是
  empty : Set
  insert : Set x Int -> Set
  isEmpty? : Set -> Bool
  contains? : Set x Int -> Bool

这种整数集 ADT 有许多可能的表示。例如，可以使用 Scheme 的表来实现它：

(define empty '())

(define (insert set val)
  (if (not (contains? set val))
      (cons val set)
      set))

(define (isEmpty? set) (null? set))

(define (contains? set val)
  (if (null? set) #f
      (if (eq? (car set) val)
          #t
          (contains? (cdr set) val))))

客户程序可以使用 ADT 值，而无需知道底层的表示法：

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

我们也可以用另一种表示方式来实现 ADT 集合，比如使用 PLAI 的 define-type 机制来创建一个变体类型，将集合编码为链表。

(define-type Set
  [mtSet]
  [aSet (val number?) (next Set?)])

(define empty (mtSet))

(define (insert set val)
  (if (not (contains? set val))
      (aSet val set)
      set))

(define (isEmpty? set) (equal? set empty))

(define (contains? set val)
  (type-case Set set
    [mtSet () #f]
    [aSet (v next)
          (if (eq? v val)
              #t
              (contains? next val))]))

前面的示例客户程序运行照旧，即使现在底层表示换掉了：

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