►程序设计方法教学包
▼2 Ht  DP/  2e教学包
►2.7 抽象:   "abstraction.rkt"
在本页中：
2.7.1 循环和解析
for/  list
for*/  list
for/  or
for*/  or
for/  and
for*/  and
for/  sum
for*/  sum
for/  product
for*/  product
for/  string
for*/  string
in-range
in-naturals
2.7.2 模式匹配
match
2.7.3 代数数据类型
define-type
type-case
  顶层  ← 前一页  上一层  后一页 → 

2.7 抽象: "abstraction.rkt"

Matthias Felleisen
及Racket-zh项目组译

 (require 2htdp/abstraction) package： htdp-lib

abstract.rkt教学包提供一些额外的抽象工具：解析（comprehension）和循环、匹配及代数数据类型。 其中大多数是其他Racket系列语言中完整功能的受限版本， 因此HtDP/2e（《程序设计方法》第二版）的学生不必纠结于复杂的语法。

HtDP/2e在一独立章节中介绍了循环和匹配，其唯一目的是让学生知悉强大语言机制的存在。

提供代数数据类型的理由是，有些人认为教授函数式编程的特性比教授普遍适用的程序设计思想更重要。

添加于package htdp-lib的1.1版本。

2.7.1 循环和解析

语法

(for/list (comprehension-clause comprehension-clause ...) body-expr)

 
comprehension-clause = (name clause-expr)
使用comprehension-clause们并行提供的值的序列计算body-expr。

comprehension-clause(解析子句)在body-expr中绑定它的name。

for/list表达式计算所有的clause-expr以生成值的序列。 如果clause-expr求值为

  • 链表，其项组成序列值；

  • 自然数n，值的序列由数字0、1、…、(- n 1)组成；

  • 字符串，序列的项为其中每个字符构成的字符串。

对于由in-range和in-naturals生成的序列，请见下文。

最后，for/list计算body-expr， 其中name ...依次绑定到由clause-expr ...确定的序列中的值。
> (for/list ((i 10))
    i)

'(0 1 2 3 4 5 6 7 8 9)

> (for/list ((i 2) (j '(a b)))
    (list i j))

'((0 a) (1 b))

> (for/list ((c "abc"))
    c)

'("a" "b" "c")

当最短的序列耗尽时，计算停止。
> (for/list ((i 2) (j '(a b c d e)))
    (list i j))

'((0 a) (1 b))

语法

(for*/list (comprehension-clause comprehension-clause ...) body-expr)

使用嵌套的comprehension-clause们提供的值的序列计算body-expr。

comprehension-clause在body-expr中， 以及后续的comprehension-clause中绑定它的name。

> (for*/list ((i 2) (j '(a b)))
    (list i j))

'((0 a) (0 b) (1 a) (1 b))

> (for*/list ((i 5) (j i))
    (list i j))

'((1 0) (2 0) (2 1) (3 0) (3 1) (3 2) (4 0) (4 1) (4 2) (4 3))

由于嵌套，计算不会在最短序列耗尽时停止， 因为comprehension-clause们会被按顺序求值：
> (for*/list ((i 2) (j '(a b c d e)))
    (list i j))

'((0 a) (0 b) (0 c) (0 d) (0 e) (1 a) (1 b) (1 c) (1 d) (1 e))

语法

(for/or (comprehension-clause comprehension-clause ...) body-expr)

和for/list一样对comprehension-clause生成的序列进行迭代。 返回第一个非#false值，如果有的话，不然返回#false。

> (for/or ([c "abcd"])
     (if (string=? "x" c) c #false))

#f

> (for/or ([c (list #false 1 #false 2)])
     c)

1

语法

(for*/or (comprehension-clause comprehension-clause ...) body-expr)

和for*/list一样对comprehension-clause生成的序列进行迭代。 返回第一个非#false值，如果有的话，不然返回#false。

> (for*/or ([i 2][j i])
     (if (> j i) (list i j) #false))

#f

语法

(for/and (comprehension-clause comprehension-clause ...) body-expr)

和for/list一样对comprehension-clause生成的序列进行迭代。 如果任何一次计算body-expr得到#false，则循环停止并返回#false； 否则，循环返回最后一次计算body-expr的结果。

> (for/and ([c '(1 2 3)])
     (if (> c 4) c #false))

#f

> (for/and ([c '(1 2 3)])
     (if (< c 4) c #false))

3

语法

(for*/and (comprehension-clause comprehension-clause ...) body-expr)

和for*/list一样对comprehension-clause生成的序列进行迭代。 如果任何一次计算body-expr得到#false，则循环停止并返回#false； 否则，循环返回最后一次计算body-expr的结果。

> (for*/and ([i 2][j i])
     (if (< j i) (list i j) #false))

'(1 0)

语法

(for/sum (comprehension-clause comprehension-clause ...) body-expr)

和for/list一样对comprehension-clause生成的序列进行迭代。 将计算body-expr所得的数值相加。

> (for/sum ([i 2][j 8])
     (max i j))

1

语法

(for*/sum (comprehension-clause comprehension-clause ...) body-expr)

和for*/list一样对comprehension-clause生成的序列进行迭代。 将计算body-expr所得的数值相加。

> (for*/sum ([i 2][j i])
     (min i j))

0

语法

(for/product (comprehension-clause comprehension-clause ...) body-expr)

和for/list一样对comprehension-clause生成的序列进行迭代。 将计算body-expr所得的数值相乘。

> (for/product ([i 2][j 3])
     (+ i j 1))

3

语法

(for*/product (comprehension-clause comprehension-clause ...) body-expr)

和for*/list一样对comprehension-clause生成的序列进行迭代。 将计算body-expr所得的数值相乘。

> (for*/product ([i 2][j i])
     (+ i j 1))

2

语法

(for/string (comprehension-clause comprehension-clause ...) body-expr)

和for/list一样对comprehension-clause生成的序列进行迭代。 使用implode收集body-expr求值所得的单字符字符串。

> (for/string ([i "abc"])
     (int->string (+ (string->int i) 1)))

"bcd"

语法

(for*/string (comprehension-clause comprehension-clause ...) body-expr)

和for*/list一样对comprehension-clause生成的序列进行迭代。 使用implode收集body-expr求值所得的单字符字符串。

> (for*/string ([i "ab"][j (- (string->int i) 90)])
     (int->string (+ (string->int i) j)))

"abcdefgbcdefghi"

函数

(in-range start end step) → sequence?

  start : natural-number/c
  end : natural-number/c
  step : natural-number/c
(in-range end) → sequence?
  end : natural-number/c
生成有限自然数序列。

如果提供了start、end和step， 序列就是start、(+ start step)、(+ start step step)、…直到总和大于或等于end。

> (for/list ([i (in-range 1 10 3)]) i)

'(1 4 7)

如果只提供了end，则start默认为0， step默认为1：
> (for/list ([i (in-range 3)])
    i)

'(0 1 2)

> (for/list ([i (in-range 0 3 1)])
    i)

'(0 1 2)

函数

(in-naturals start) → sequence?

  start : natural-number/c
生成start开始的无限自然数序列。

> (define (enumerate a-list)
    (for/list ([x a-list][i (in-naturals 1)])
      (list i x)))
> (enumerate '(Maxwell Einstein Planck Heisenberg Feynman))

'((1 Maxwell) (2 Einstein) (3 Planck) (4 Heisenberg) (5 Feynman))

> (enumerate '("Pinot noir" "Pinot gris" "Pinot blanc"))

'((1 "Pinot noir") (2 "Pinot gris") (3 "Pinot blanc"))

2.7.2 模式匹配

语法

(match case-expr (pattern body-expr) ...)

 
pattern = name
  | literal-constant
  | (cons pattern pattern)
  | (name pattern ...)
  | (? name)
和cond一样求值，将case-expr的值按顺序与所有pattern匹配。 第一个成功的匹配触发对应body-expr的求值，其值即是整个match表达式的值。

常见的文字常量是数字、字符串、符号和'()。

每个包含name的模式都会在相应的body-expr中绑定这些名称。

值和模式的匹配根据以下规则进行。如果模式是

  • name，它匹配任何值；

  • literal-constant，它只匹配本文常量；

  • (cons pattern_1 pattern_2)，它匹配cons实例， 并且其first/rest字段能和pattern_1及pattern_2匹配；

  • (name pattern ...)，它匹配name结构体类型的实例， 并且其字段值能和pattern ...匹配；

  • (? name)，如果name是个谓词函数，并且它对给定的值返回#true， 那么匹配成功。

此外，如果给定的模式是name、值是V， 那么在计算相应的body-expr时，name代表V。

以下match表达式将cons第二个位置的'()和其他值区分开：
> (define (last-item l)
     (match l
       [(cons lst '()) lst]
       [(cons fst rst) (last-item rst)]))
> (last-item '(a b c))

'c

使用?，match可以用谓词来区分任意值：
> (define (is-it-odd-or-even l)
     (match l
       [(? even?) 'even]
       [(? odd?)  'odd]))
> (is-it-odd-or-even '1)

'odd

> (is-it-odd-or-even '2)

'even

match表达式也可以处理结构体实例：
> (define-struct doll (layer))
> (define (inside a-doll)
    (match a-doll
      [(? symbol?) a-doll]
      [(doll below) (inside below)]))
> (inside (make-doll (make-doll 'wood)))

'wood

但请注意，模式仅使用doll（结构体类型的名称）， 而不是make-doll（构造函数名称）。

2.7.3 代数数据类型

语法

(define-type type (variant (field predicate) ...) ...)

 
type = name
     
variant = name
     
field = name
     
predicate = name
定义结构体类型variant ...，其中字段为field ...。 此外，它会定义检查字段值满足指定谓词的构造函数。最后， 它还定义type为所有variant结构体类型的并集的名称， 定义type?为判断值是否属于此类值的谓词。

考虑以下的类型定义：
(define-type BTree
  (leaf (info number?))
  (node (left BTree?) (right BTree?)))
它定义了两种结构体类型：
(define-struct leaf (info))
(define-struct node (left right))
当应用于除数值之外的任何其他值时make-leaf构造函数会抛出错误， 而make-node仅接受BTree的实例。 最后，BTree?是识别这种实例的谓词：
> (make-leaf 42)

(leaf 42)

> (make-node (make-leaf 42) (make-leaf 21))

(node (leaf 42) (leaf 21))

> (BTree? (make-node (make-leaf 42) (make-leaf 21)))

#t

调用构造函数于错误类型的值时会失败：
> (make-leaf 'four)

make-leaf: contract violation

  expected: (or/c undefined? number?)

  given: 'four

  in: the 1st argument of

      (-> (or/c undefined? number?) leaf?)

  contract from: make-leaf

  blaming: use

   (assuming the contract is correct)

  at: program:2.0

语法

(type-case type case-expr (variant (field ...) body-expr) ...)

像cond一样求值，将case-expr的值按顺序与所有variant匹配。 第一个成功的匹配触发对应body-expr的求值，其值是整个类型type-case的值。

type-case表达式还确保 （1）variant子句的集合覆盖type中的所有变体的结构体类型定义，以及 （2）每个variant子句指定的字段数与type定义指定的一样多。

在上述BTree类型定义的作用域内：
(define (depth t)
  (type-case BTree t
    [leaf (info) 0]
    [node (left right) (+ (max (depth left) (depth right)) 1)]))
这个函数定义使用了BTree的type-case，其中包含两个子句： 一个用于leaf，一个用于node。该函数计算输入树的深度。

> (depth (make-leaf 42))

0

> (depth (make-node (make-leaf 42) (make-leaf 21)))

1

  顶层  ← 前一页  上一层  后一页 →