UBC - CPSC 110 - Compound Data

我们在上一章体验了 Racket 语言当中十分有趣的big-bang表达式，但在尝试设计一个世界的时候，其实会发现状态本身可能并不简单。交通灯只是一个枚举、座位号只是一个区间，那么像一个包含经验值、金币数等多方面的玩家数据呢？它该是什么。

本章会学习如何设计复合数据定义，以表示由两个或多个自然连接的值组成的信息，以及如何将这些数据用作 HtDW 问题中的世界状态。

学习目标

能够识别应表示为复合数据的领域信息
能够读写define-struct定义
能够设计接受和/或返回复合数据的函数
能够设计使用复合世界状态的世界程序

以下内容涉及到的edX链接均不保证可访问性

define-struct

在之前，我们总是操作一些原子类型或者是稍显复杂的枚举、区间等，但对于复杂情况，比如表示x和y坐标，一个人的姓和名，我们该怎么做？

Racket 有一个能创建复合类型的表达式，即define-struct。以二维坐标为例，我们可以写出：(define-struct pos (x y))。这里pos是结构名，而后面的(x y)一类都是字段名。

尝试在一个空白的程序中运行这段代码，你会发现没有任何输出，这是因为define-struct和define一样，都是定义用的代码，不会实际产出什么的东西。也可以将pos理解为我们创造的复合类型，里面包含一个x值和一个y值。

我们总需要以某种方式得到一个pos类型的东西，可以为它写一个构造器 (Constructor)。

约定俗成的是，当你写出了pos这种复合类型，你同时得到了make-pos表达式，你可以往里面传两个值（对应x和y），来获得一个pos类型的值：(define P1 (make-pos 3 6))。

这时候P1就是一个x=3且y=6的pos类型值了。那么我们又该如何获取它的x和y呢？

1 2	(pos-x P1) (pos-y P1)

运行后会发现交互区出现了3和6，也就是说不仅仅是make-pos，pos-x和pos-y也出现了。

接着就是和之前各种带?的表达式一样，我们也可以通过pos?表达式来判断后面的值是不是pos类型，比如：

1 2	(pos? P1) ; true (pos? "hello") ; false

Compound Data Definitions

本节会像之前第一次学到数据定义一样，细致地介绍如何定义一个复合类型。在此之前，下载来自edX的 compound-starter.rkt 文件。

compound-starter.rkt

这道题要求我们设计一个数据结构，用于记录曲棍球员的姓和名，也就是说这两个值应该被绑在一块，形成一个复合类型。

首先，我们来尝试走一遍流程，先是类型定义本身：(define-struct player (fn ln))。

和普通数据定义一样，我们也要写注释声明Player：;; Player is (make-player String String)，这样我们既注明了它的构造器，也明确了fn和ln的类型是String。

那么我们该如何解释它呢？我们应该从player、fn和ln这三个名字开始，因为对于其他人来说他们可能并不知道这三个名字是什么意思：

1
2
3

;; interp. (make-player fn ln) is a hockey player with
;;          fn is the first name
;;          ln is the last name

然后就是一些例子，可以随便起一些名字：

1 2	(define P1 (make-player "Bobby" "Orr")) (define P2 (make-player "Wayne" "Gretzky"))

接下来就是函数模板，既然它是个复合类型，那么获取它的两个字段值也是它模板函数需要用到的部分：

1
2
3

(define (fn-for-player p)
    (... (player-fn p)     ; String
         (player-ln p)))   ; String

但它的模板规则就是带两个字段的复合类型：

1 2	;; Template rules used: ;; - Compound: 2 fields

完整定义如下：

(define-struct player (fn ln))
;; Player is (make-player String String)
;; interp. (make-player fn ln) is a hockey player with
;;          fn is the first name
;;          ln is the last name
(define P1 (make-player "Bobby" "Orr"))
(define P2 (make-player "Wayne" "Gretzky"))

(define (fn-for-player p)
    (... (player-fn p)     ; String
         (player-ln p)))   ; String
         
;; Template rules used:
;;   - Compound: 2 fields

Practice Problems

Compound P1 - Movie
- movie-starter.rkt
- movie-solution.rkt
Compound P3 - Student
- student-starter.rkt
- student-solution.rkt

Compound P1 - Movie 题解

预计耗时：25 min / 中等

这道题有两个部分，分别是数据定义和函数设计。让我们先来看数据定义部分：你需要定义一个movie类型来记录一部电影的名字、预算和发布时间。

既然是复合类型，我们就需要使用define-struct表达式，后面跟三个不同类型的名字(title budget year)，同时标注这些类型是一个字符串和两个自然数，并给出解释：

1
2
3

(define-struct movie (title budget year))
;; Movie is (make-movie String Natural Natural)
;; interp. a movie with title, budget in USD, and year released

借助构造器make-movie写三个例子：

1
2
3

(define M1 (make-movie "Titanic" 200000000 1997))
(define M2 (make-movie "Avatar" 237000000 2009))
(define M3 (make-movie "The Avengers" 220000000 2012))

因为它是带有三个字段的复合类型，我们写的模板函数也要照顾到这三个字段，通过movie-字段名来展开三个字段：

(define (fn-for-movie m)
  (... (movie-title m)    ;String
       (movie-budget m)   ;Natural
       (movie-year m)))   ;Natural

以及比较好写的复合类型模板规则：

1 2	;; Template rules used: ;; - compound: 3 fields

函数定义部分代码：

(define-struct movie (title budget year))
;; Movie is (make-movie String Natural Natural)
;; interp. a movie with title, budget in USD, and year released

(define M1 (make-movie "Titanic" 200000000 1997))
(define M2 (make-movie "Avatar" 237000000 2009))
(define M3 (make-movie "The Avengers" 220000000 2012))

#;
(define (fn-for-movie m)
  (... (movie-title m)    ;String
       (movie-budget m)   ;Natural
       (movie-year m)))   ;Natural

;; Template rules used:
;; - compound: 3 fields

数据定义部分结束，接下来是函数设计：判断传入的两个Movie的发布时间哪个更新，返回其名字。

从题目能理解出它的传入值类型是两个Movie，而返回值类型是String。同时函数的目的就是：determine which of two given movies was released most recently。

可以随意写一些测试，记得引用一开始的M1、M2和M3：

1 2	(check-expect (chronological-movie M1 M2) "Avatar") (check-expect (chronological-movie M3 M2) "The Avengers")

定义它的桩函数：; (define (chronological-movie m1 m2) "") ; stub。由于这里的实现与函数模板差别大，我们就不再写use template from之类的东西，而是现写新模板：函数名就是fn-for-movie，传入参数m1和m2，之后需要写上这俩所有的字段名：

(define (fn-for-movie m1 m2)
  (... (movie-title m1)
       (movie-budget m1)
       (movie-year m1)
       (movie-title m2)
       (movie-budget m2)
       (movie-year m2)))

最后实现函数，函数名和桩函数一样。对于函数体部分，我们只需要使用if表达式判断两个movie-year的大小，最后看情况返回对应movie的title就行：

(define (chronological-movie m1 m2)
  (if (> (movie-year m1) (movie-year m2))
      (movie-title m1)
      (movie-title m2)))

函数设计代码如下：

;; Movie Movie -> String
;; determine which of two given movies was released most recently
(check-expect (chronological-movie M1 M2) "Avatar")
(check-expect (chronological-movie M3 M2) "The Avengers")

; (define (chronological-movie m1 m2) "")   ; stub

#;
(define (fn-for-movie m1 m2)
  (... (movie-title m1)
       (movie-budget m1)
       (movie-year m1)
       (movie-title m2)
       (movie-budget m2)
       (movie-year m2)))

(define (chronological-movie m1 m2)
  (if (> (movie-year m1) (movie-year m2))
      (movie-title m1)
      (movie-title m2)))

Compound P3 - Student 题解

预计耗时：25 min / 中等

这道题也是相同的两个部分。让我们先来看数据定义部分：你需要定义一个Student，记录学生的名字、年级（从1到12）和是否存在过敏（为了准备出游的午餐）。

ps: 由于是否过敏这一项是布尔类型的，所以它会带问号

类型名就是student，带有三个字段名(name grade allergies?)，定义为Student is (make-student String Natural[1, 12] Boolean)，解释是interp. a student with a name, in grade 1-12, and true if they have allergies。之后写一些例子：

(define-struct student (name grade allergies?))
;; Student is (make-student String Natural[1, 12] Boolean)
;; interp. a student with a name, in grade 1-12, and true if they have allergies

(define S1 (make-student "Bob" 2 true))
(define S2 (make-student "Hannah" 5 false))

同样，它的函数模板也是用需要标明所有传入的字段，以及它的函数模板规则：

(define (fn-for-student s)
  (... (student-name s)         ;String
       (student-grade s)        ;Natural[1, 12]
       (student-allergies? s))) ;Boolean

;; Template rules used:
;; - compound: 3 fields

数据定义部分结束，接下来是函数设计：考虑到六年级及以下学生的过敏是很危险的，我们需要判断学生是否属于这种情况并添加到特殊列表中（这个列表只是用来起名字的，不需要实际实现）。

从题目能理解出它的传入值类型是Student，而返回值类型是Boolean。同时函数的目的就是： produce true if the given student is at or below grade 6 and has allergies。

考虑到函数存在两个判断，我们需要多写一些测试：

(check-expect (add-name? S1) true)
(check-expect (add-name? S2) false)
(check-expect (add-name? (make-student "Joanne" 10 true)) false)
(check-expect (add-name? (make-student "John" 11 false)) false)

定义它的桩函数：;(define (add-name? s) true) ; stub，并且声明将会用Student的函数模板：;<use template from Student>

接下来将数据定义部分的函数模板复制下来，将函数名改为add-name?，并且根据测试来完善函数体。对于六年级及以下和是否有过敏，很显著的是我们需要使用and来进行与的判断：

1
2
3

(define (add-name? s)
  (and (<= (student-grade s) 6)
       (student-allergies? s)))

ps: 如果用了if也是可以的

函数设计代码如下：

;; Student -> Boolean
;; produce true if the given student is at or below grade 6 and has allergies
(check-expect (add-name? S1) true)
(check-expect (add-name? S2) false)
(check-expect (add-name? (make-student "Joanne" 10 true)) false)
(check-expect (add-name? (make-student "John" 11 false)) false)

;(define (add-name? s) true)   ; stub
; Template from Student

(define (add-name? s)
  (and (<= (student-grade s) 6)
       (student-allergies? s)))

HtDW With Compound Data

本节我们将基于复合类型设计一个世界。在之前，我们设计过带有一只猫的世界，现在我们将从一头牛开始。这头牛走出栅栏，过一会又转身回来。你会发现这个行为和猫不同 —— 猫只有一个轴上的坐标变化，而牛似乎还会涉及到方向。

下载来自edX的 cowabunga-starter.rkt 文件。

cowabunga-starter.rkt

以下是图中两头牛的素材：

左边的牛

右边的牛

这道题很长，简单来说就是有头牛碰到屏幕边缘就来回走，用户也可以按下空格键来手动改变方向。按照上一章的步骤，我们先开始分析：

常量：
- 窗口的长宽是基本的，不会变
- 牛在往返走，故它的y坐标也不会变
- 牛本身的图像（左和右）和空白背景不会变
变量：
- 牛的x坐标在来回变化
- 牛每次碰壁需要转向，转向本身只会改变牛的图像，而它的速度被改变了（方向上）
big-bang选项：
- on-tick和on-draw是最基本的
- on-key用来响应用户按下空格键的行为

cowabunga-starter.rkt 分析

分析明白后，我们可以从edX的 cowabunga-v0.rkt 文件开始，这个代码文件是本节项目的第一个，帮我们写了注释和常量定义。

那我们就从数据定义开始。由于牛的变化的量是它的x坐标和速度，它需要一个复合类型把它们装起来：(define-struct cow (x dx))，定义为：Cow is (make-cow Natural[0, WIDTH], Integer)。

它的解释需要更加详尽：

;; interp. (make-cow x dx) is a cow with x coordinate x and x velocity dx
;;         the x is the center of the cow
;;         x  is in screen coordinates (pixels)
;;         dx is in pixels per tick

之后就是它的例子，考虑到世界全程这头牛要么向左走要么向右走，我们就写这两种情况的例子：

1 2	(define C1 (make-cow 10 3)) ; at 10, moving left -> right (define C2 (make-cow 20 -4)) ; at 20, moving left <- right

以及它的函数模板和模板规则：

#;
(define (fn-for-cow c)
  (... (cow-x c)    ;Natural[0, WIDTH]
       (cow-dx c))) ;Integer

;; Template rules used:
;;  - compound: 2 fields

最后能得到edX的 cowabunga-v1.rkt 文件，数据定义部分代码如下：

(define-struct cow (x dx))
;; Cow is (make-cow Natural[0, WIDTH] Integer)
;; interp. (make-cow x dx) is a cow with x coordinate x and x velocity dx
;;         the x is the center of the cow
;;         x  is in screen coordinates (pixels)
;;         dx is in pixels per tick
;;
(define C1 (make-cow 10  3)) ; at 10, moving left -> right
(define C2 (make-cow 20 -4)) ; at 20, moving left <- right
#;
(define (fn-for-cow c)
  (... (cow-x c)    ;Natural[0, WIDTH]
       (cow-dx c))) ;Integer

;; Template rules used:
;;  - compound: 2 fields

为了效率，我们接下来直接从edX的 cowabunga-v2.rkt 文件开始，这里帮我们写好了big-bang相关的表达式和桩函数。

先从next-cow函数开始，阅读它的目的能发现它需要让牛的x坐标增长，并根据是否在边缘来改变速度的方向。

它的测试需要考虑到三种情况：远离边缘时、到达边缘时、试图越过边缘时。

(check-expect (next-cow (make-cow 20           3)) (make-cow (+ 20 3)  3)) ;away from edges
(check-expect (next-cow (make-cow 20          -3)) (make-cow (- 20 3) -3))

(check-expect (next-cow (make-cow (- WIDTH 3)  3)) (make-cow WIDTH     3)) ;reaches edge
(check-expect (next-cow (make-cow 3           -3)) (make-cow 0        -3))

(check-expect (next-cow (make-cow (- WIDTH 2)  3)) (make-cow WIDTH    -3)) ;tries to pass edge
(check-expect (next-cow (make-cow 2           -3)) (make-cow 0         3))

然后就是桩函数：;(define (next-cow c) c) ;stub以及来自cow的函数模板，将它复制过来并改名。考虑到我们需要处理三种情况，可以使用cond表达式，在Q和A中都写上cow的两个字段：

(define (next-cow c)
  (cond [(... (cow-x c)
              (cow-dx c))
         (... (cow-x c)
              (cow-dx c))]
        [(... (cow-x c)
              (cow-dx c))
         (... (cow-x c)
              (cow-dx c))]
        [(... (cow-x c)
              (cow-dx c))
         (... (cow-x c)
              (cow-dx c))]))

ps: 括号恐惧症犯了

这里就是cond的三种情况，分别处理：

碰到屏幕右边
碰到屏幕左边
正常移动

第一种情况，我们需要判断下一刻牛会不会撞上右边缘，这个逻辑该怎么写呢？如果牛的当前坐标和牛当前的速度相加发现能达到WIDTH，是不是意味着牛下一秒会撞到右边缘。之后的处理方法就是将牛安全的放在边缘，并让当前的速度方向取反：

1 2	[(> (+ (cow-x c) (cow-dx c)) WIDTH) (make-cow WIDTH (- (cow-dx c)))]

第二种情况和第一种就很像了，就是牛向左走的碰到左边缘的时候。这时候由于速度已经是负数了，那么我们直接将牛的x坐标和速度相加，判断它是否达到0以下就行了，同时将牛放到0的位置并以方向相反的速度移动：

1 2	[(< (+ (cow-x c) (cow-dx c)) 0) (make-cow 0 (- (cow-dx c)))]

第三种情况就很简单了，就是牛在屏幕中晃悠：

1
2
3

[else
    (make-cow (+ (cow-x c) (cow-dx c))
              (cow-dx c))]

最后的函数体代码如下：

(define (next-cow c)
  (cond [(> (+ (cow-x c) (cow-dx c)) WIDTH) (make-cow WIDTH (- (cow-dx c)))]
        [(< (+ (cow-x c) (cow-dx c)) 0)     (make-cow 0     (- (cow-dx c)))]
        [else
         (make-cow (+ (cow-x c) (cow-dx c))
                   (cow-dx c))]))

让我们从edX的 cowabunga-v3.rkt 文件开始，这里已经做好了next-cow。这次我们开始写剩下的部分。

先是render-cow，先写它的测试：

(check-expect (render-cow (make-cow 99 3))
              (place-image RCOW 99 CTR-Y MTS))
(check-expect (render-cow (make-cow 33 -3))
              (place-image LCOW 33 CTR-Y MTS))

复合数据测试

在测试复合数据时，尽可能让每个字段多变一变，这样能测试到更多东西。

以及桩函数：;(define (render-cow c) MTS) ;stub。从cow的函数模板复制下来，改名：

; took template from Cow
(define (render-cow c)
  (... (cow-x c)
       (cow-dx c)))

抛开显示哪头牛不谈，我们先用place-image显示牛本身：

1 2	(define (render-cow c) (place-image ... (cow-x c) CTR-Y MTS))

接下来就是封装的魅力了。对于显示哪头牛我们当然可以通过直接在place-image后面写个if判断方向正不正来返回对应的牛。但我们要遵循单一职责原则 —— 在这里可以解释为一个函数不要干超过它预设职责的事情。

对于选择牛图像这件事，我们可以把它放在另一个函数里面，称作choose-image，传入一个cow。

先写上函数的签名Cat -> Image，目的produce RCOW or LCOW depending on direction cow is going，以及特有的!!!。

它的测试需要包括向左走和向右走牛的图像选择：

1
2
3

(check-expect (choose-image (make-cow 10 3))  RCOW)
(check-expect (choose-image (make-cow 11 -3)) LCOW)
(check-expect (choose-image (make-cow 11 0))  LCOW)  ; 默认情况

之后从cow的模板函数复制过来，然后使用if表达式判断传入cow的dx是否为正，如果是那么就返回RCOW，否则就是LCOW：

(define (choose-image c)
  (if (> (cow-dx c) 0)
      RCOW
      LCOW))

最后的键盘响应就不细说了：

;; Cow KeyEvent-> Cow
;; reverse direction of cow travel when space bar is pressed
;; !!!
;(define (handle-key c ke) c) ;stub

(define (handle-key c ke)
  (if (string=? ke " ")
      (make-cow (cow-x c) (- (cow-dx c)))
      c))

回过头来，我们做了choose-image的封装，那么(place-image ... (cow-x c) CTR-Y MTS)这个地方的...就可以变成(choose-image c)了。

如果不出意外，运行测试会成功，然后在交互区向main函数随便传个cow就行，比如：(main (make-cow 10 5))，回车后就能看到效果了。

Practice Problems

Compound P9 - Water Balloons
- water-balloon-starter.rkt
- water-balloon-solution.rkt

Compound P9 - Water Balloons 题解

预计耗时：90 min / 困难

这道题看似复杂，实际上就是一个图像从左移动到右，同时在旋转。

那么经过分析，我们可以发现以下常量：

有关窗口的宽高、空白场景
有关气球本身的图像，线速度和角速度，以及它不变的y坐标


(define WIDTH  600)
(define HEIGHT 300)

(define CTR-Y (/ HEIGHT 2))

(define LINEAR-SPEED 2)  
(define ANGULAR-SPEED 3) ;optional

(define MTS (rectangle WIDTH HEIGHT "solid" "white"))

(define WATER-BALLOON <气球图像>)

然后是数据定义，我们将这个世界的状态定为BalloonState，含有x和a两个字段，分别意为x坐标和角度：

(define-struct bs (x a))
;; BalloonState is (make-bs Number Number)
;; interp. The state of a tossed balloon.
;;         x is the x-coordinate in pixels
;;         a is the angle of rotation in degrees
;;
(define BS1 (make-bs 10 0))
(define BS2 (make-bs 30 15))

它的函数模板和规则如下：

#;
(define (fn-for-balloon-state bs)
  (... (bs-x bs)
       (bs-a bs)))

;; Template rules used:
;; - compound: 2 fields

然后就是函数设计部分，这一部分首先需要考虑的就是整体的main函数和里面的big-bang表达式。我们将on-tick的函数命名为next-bs、to-draw的函数命名为render-bs、以及on-key的函数命名为reset-bs。

main函数本身就是BalloonState -> BalloonState的持续运行的函数，用于实现动画。它的起始状态应为(main (make-bs 0 0))：

;; BalloonState -> BalloonState
;; run the animation, starting with initial balloon state bs.
;; Start with (main (make-bs 0 0))
;; <no tests for main functions>

(define (main bs)
  (big-bang bs
            (on-tick next-bs)
            (to-draw render-bs)
            (on-key  reset-bs)))

之后就是每个函数的处理了。对于next-bs函数，我们知道它的签名也是BalloonState -> BalloonState，目的是调整下一次气球的线速度和角速度值。只需要让当前bs-x与线速度相加，bs-a与角速度相减（加减与旋转方向有关）就能处理：

;; BalloonState -> BalloonState
;; advance bs by LINEAR-SPEED and ANGULAR-SPEED
(check-expect (next-bs (make-bs 1 12))
              (make-bs (+ 1 LINEAR-SPEED) (- 12 ANGULAR-SPEED)))

;(define (next-bs bs) bs)  ;stub
; Template from BalloonState

(define (next-bs bs)
  (make-bs (+ (bs-x bs) LINEAR-SPEED)
           (- (bs-a bs) ANGULAR-SPEED)))

这次的渲染函数render-bs需要注意，我们会使用rotate表达式来渲染旋转过的图像，但总体上还是place-image的。

但我们刚刚的实现 —— (- 12 ANGULAR-SPEED) —— 没有考虑小于0或者大于360的情况，也就是说角度会超出可用范围（这里是这样的）。我们需要使用某种方法来让这个值始终在360以内。

这时候就需要使用modulo表达式来取余。会发现比如361，如果使其对360取余，那么值就是1。如果是720，那就是0。我们可以通过这种方法来让值始终可用：

;; BalloonState -> Image
;; Produces the bs at height bs-x rotated (remainder bs-a 360) on the MTS
(check-expect (render-bs (make-bs 1 12))
              (place-image (rotate 12 WATER-BALLOON)
                           1
                           CTR-Y
                           MTS))
(check-expect (render-bs (make-bs 10 361))
              (place-image (rotate 1 WATER-BALLOON)
                           10
                           CTR-Y
                           MTS))

; (define (render-bs bs) MTS)

; Template from BalloonState
(define (render-bs bs)
  (place-image (rotate (modulo (bs-a bs) 360) WATER-BALLOON)
               (bs-x bs)
               CTR-Y
               MTS))

按空格键重置状态就很好写了，和之前都差不多：

;; BalloonState KeyEvent -> BalloonState
;; Resets the program so the balloon is back at the top, unrotated, when space bar is pressed
(check-expect (reset-bs (make-bs 1 12) " ")
              (make-bs 0 0))
(check-expect (reset-bs (make-bs 1 12) "left")
              (make-bs 1 12))

; (define (reset-bs bs key) bs)

; Template from KeyEvent
(define (reset-bs bs key)
  (cond [(key=? " " key) (make-bs 0 0)]
        [else bs]))