数据修改
十二课
之前的课程中，我们已经讨论数据抽象的几个重要组成部分：构造器 (constructors)、选择器 (selectors)、操作 (operations) 以及契约 (contract)。只要按照数据的契约来使用、操作数据，程序就会向着我们预想中的方向运行。为了达到目的，我们需要反复从旧数据中构造新数据。要是我们能够直接修改旧数据，情况又会发生什么样的变化？本节课将引入数据修改 (Data Mutation) ，丰富我们的数据抽象思路。
替代模型 (substitution model) 假设我们使用函数式编程 (functional programming)，没有数据变动和副作用，每段程序都像一个数学函数，无论在什么时候，都准确地将确定的输入映射到确定的输出上。但如果我们引入数据修改，每段程序的输出结果就不仅仅只依赖于输入，还依赖于程序被执行时的环境。举例如下：
(define x 10)
(+ x 5)
> 15
(set! x 94)
(+ x 5)
> 99我们将看到
引入数据修改使得许多事情变得容易，但会提高犯错的可能性。
Pair/List Mutation
除了构造器、选择器、操作外，数据抽象可能还包含修改器 (mutators)。将数据变动引入到 Scheme 的 pair/list 中，可以得到如下的 pair/list 数据抽象：
；constructor
(cons x y) ; creates a new pair p
; selectors
(car p) ; returns car part of pair
(cdr p) ; returns cdr part of pair
; mutators
(set-car! p new-x) ; changes car pointer in pair
(set-cdr! p new-y) ; changes cdr pointer in pair
; Pair, anytype -> undef ; side-effect only其中，set-car! 和 set-cdr! 分别修改 pair 的 car 部分和 cdr 部分指针指向的数据，而且这两种方法只有副作用，没有返回值，因此其返回值是不确定的 (unspecified)。
例1：
mutation 给我们编程带来方便的同时引入问题，需要我们格外注意：
(define a (list 1 2))
(define b a)
; a ==> (1 2)
; b ==> (1 2)
(set-car! a 10)
; a ==> (10 2)
; b ==> (10 2)由于 a 和 b 指向同一块内存，修改 a 的同时，也会修改 b，如下图所示：
因此我们需要在充分了解 mutation 的基础上加以使用。
例2：
如下图所示修改 x 对应的 list：
可以这样实现：
(define x (list 'a 'b))
(set-car! (cdr x) (list 1 2))Equivalence and Identity
在表示相等关系时，我们常常有这样两个问题：
a 和 b 是否很像？
a 和 b 是否是同一个？
如果 a 和 b 很像，那么二者至少表面看起来给人相似的感觉，这就是 equivalence。
如果 a 和 b 是同一个，那么二者实际上指代同一个物体，这就是 identity。
; equivalence
; a、b 是否是同一个
(eq? a b)
; identity
; a、b 是否长得像
(equal? a b)例1：Stack Data Abstraction
Stack 数据抽象的几个组成部分如下所示：
; constructor
(make-stack) ; returns an empty stack
; selectors
(top stack) ; returns current top element from a stack
; operations
(insert stack elt) ; returns a new stack with the element added to the top of the stack
(delete stack) ; returns a new stack with the top element removed from the stack
(empty-stack? stack) ; returns #t if no elements, #f otherwise
; contract
; if s is a stack, created by (make-stack) and subsequent stack procedures, where i is the
; number of insertions and j is the number of deletions, then
; 1. if j > i : then it is an error
; 2. if j = i : then (empty-stack? s) is true, and (top s) and (delete s) are errors
; 3. if j < i : then (empty-stack? s) is false and (top (delete (insert s val))) = (top s)
; 4. if j <= i: then (top (insert s val)) = val for any val.实现1：利用 list
; constructor
(define (make-stack) nil)
; predicator
(define (empty-stack? stack) (null? stack))
; operations
(define (insert stack elt) (cons elt stack))
(define (delete stack)
(if (empty-stack? stack)
(error "stack underflow - delete")
(cdr stack)))
; selectors
(define (top stack)
(if (empty-stack? stack)
(error "stack underflow - top")
(car stack)))利用 list 直接实现，符合上文中的数据抽象的各个部分。但是我们每次 insert、delete 之后都会生成新的 stack，而并非原来的那个 stack。因此用 eq? 来判断两个 insert 或者 delete 操作前后的 stack 会得到 false。但我们在使用 stack 的过程中，更希望 stack 自始至终是同一个 stack，既符合直觉也能使得操作更加方便。这一切将在引入 mutation 之后得以解决……
实现2：利用 mutators
首先我们需要引入 tag，它有两个好处：
defensive programming
提供 identity --- 试想如果没有 tag，我们将无法做到每次都返回同一个 stack，因为 insert 将改变 list 的 identity，除非我们自己利用 set! 重新将新的 stack 绑定到原来的 name 上。
; constructor
(define (make-stack) (cons 'stack nil))
; predicators
(define (stack? stack)
(and (pair? stack) (eq? 'stack (car stack))))
(define (empty-stack? stack)
(if (not (stack? stack))
(error "object not a stack: " stack)
(null? (cdr stack))))
; mutators
(define (insert! stack elt)
(cond ((not (stack? stack))
(error "object not a stack: " stack))
(else
(set-cdr! stack (cons elt (cdr stack)))
stack)))
(define (delete! stack)
(if (empty-stack? stack)
(error "stack underflow - delete")
(set-cdr! stack (cddr stack)))
stack)
; selector
(define (top stack)
(if (empty-stack? stack)
(error "stack underflow - top")
(cadr stack)))例2：Queue Data Abstraction
queue 数据抽象的几个组成部分如下：
; constructor
(make-queue) returns an empty queue
; selectors
(front-queue q) returns the object at the front of the queue. If queue is empty signals error
; mutators
(insert-queue q elt) returns a queue with elt at the rear of the queue
(delete-queue q) returns a queue with the item at the front of the queue removed
; operations/predicators
(empty-queue? q) tests if the queue is empty
; (queue? q) tests if the object is a queue
; contracts
; if q is a queue, created by (make-queue) and subsequent queue procedures, where i is the number
; of insertions, j is the number of deletions, and x_i is the i-th item inserted into q, then
; 1. if j > i: then it is an error
; 2. if j = i: then (empty-queue? q) is true, and (front-queue q) and (delete-queue q) are errors
; 3. if j < i: then (front-queue q) = x_(j+1)实现1：没有 mutation
; constructor
(define (make-queue) nil)
; predicator
(define (empty-queue? q) (null? q))
; selector
(define (front-queue) q)
(if (empty-queue? q)
(error "front of empty queue: " q)
(car q)))
; mutators
(define (delete-queue q)
(if (empty-queue? q)
(error "delete of empty queue: " q)
(cdr q)))
(define (insert-queue q elt)
(if (empty-queue? q)
(cons elt nil)
(cons (car q) (insert-queue (cdr q) elt))))其中 insert-queue 的时间、空间复杂度皆为 O(n)
实现2：mutation
为了减少 insert-queue 的复杂度，我们在引入 tag 的同时，在 queue 中加上队首 (front )和队尾 (rear) 指针:
; helpers, hidden inside abstraction
(define (front-ptr q) (cadr q))
(define (rear-ptr q) (cddr q))
(define (set-front-ptr! q item)
(set-car! (cdr q) item))
(define (set-rear-ptr! q item)
(set-cdr! (cdr q) item))
; constructor
(define (make-queue)
(cons 'queue (cons nil nil)))
; predicator
(define (queue? q)
(and (pair? q) (eq? 'queue (car q))))
(define (empty-queue? q)
(if (not (queue? q))
(error "object not a queue: " q)
(null? (front-ptr q))))
; selector
(define (front-queue) q)
(if (empty-queue? q)
(error "front of empty queue: " q)
(car (front-ptr q))))
; mutators
(define (delete-queue q)
(cond ((empty-queue? q)
(error "delete of empty queue: " q))
(else
(set-front-ptr! q
(cdr (front-ptr q)))
q)))
(define (insert-queue q elt)
(let ((new-pair (cons elt nil)))
(cond ((empty-queue? q)
(set-front-ptr! q new-pair)
(set-rear-ptr! q new-pair)
q)
(else
(set-cdr! (rear-ptr q) new-pair)
(set-rear-ptr! q new-pair)
q))))这时候，在获得 identity 的同时，insert-queue 的复杂度降到了 O(1)
参考
Last updated