本章会涉及到更加复杂的数据结构设计,在很多时候我们不会仅靠一个数据定义就解决问题。

学习目标

  • 能够预测和识别数据定义中的引用与操作该数据的函数中的辅助函数调用之间的对应关系
以下内容涉及到的edX链接均不保证可访问性

The Reference Rule

P1

下载来自edX的 tuition-graph-starter.rkt 文件

tuition-graph-starter.rkt
tuition-graph-starter.rkt

这道题简单来说就是帮助一个人选择上哪所大学,其中有个很重要的考虑因素就是学费,也想将学费的对比通过柱状图可视化出来。

第一个面临的问题就是定义一个能够涵盖不同大学学费的数据结构。之后还需要设计一个用来生成柱状图的函数。最后写一个找到最低学费并给出判断的函数。

首先这不需要设计一个世界,只是图像绘制加一些分析而已。

在定义数据类型之前,我们先在代码文件顶部写上(require 2htdp/image)以加入图像支持。

构思一遍程序设计的全过程,我们可以提前为柱状图这个图像写一些常量:

1
2
3
4
5
(define FONT-SIZE 24)
(define FONT-COLOR "black")
(define Y-SCALE 1/200)
(define BAR-WIDTH 30)
(define BAR-COLOR "lightblue")

由于学费通常在$20,000左右,而我们的显示器通常难以容纳数以万计的像素,故其中Y-SCALE是很必要的,设置成比如1/200的值可以让学费的值变得可被直观比较。


接下来就是数据结构设计,我们可以记录每个学校的名字和学费:

1
2
3
(define-struct school (name tuition))
;; School is (make-school String Natural)
;; interp. name is the school's name, tuition is international student's tuition in USD

以及它的例子,填上你喜欢的学校也是可以的:

1
2
3
(define S1 (make-school "School1" 27797))
(define S2 (make-school "School2" 23300))
(define S3 (make-school "School3" 28500))

对于函数模板,需要记住要把School的两个字段都算上:

1
2
3
4
5
6
(define (fn-for-school s)
(... (school-name s)
(school-tuition)))

;; Template rules used:
;; - compound: (make-school String Natural)

School只是一个元素,我们需要的数据结构还需要能把一串学校给记录下来。我们就称其为ListOfSchool,里面的每个元素类型则是我们自定义的School,回忆之前定义列表的过程:

1
2
3
4
5
6
;; ListOfSchool is one of:
;; - empty
;; - (cons School ListOfSchool)
;; interp. a list of schools
(define LOS1 empty)
(define LOS2 (cons S1 (cons S2 (cons S3 empty))))

在之前,我们只会在列表中遇到一个自我引用,即其自身包含与其相同类型的值。而这里我们将它的元素类型也变成自定义的了。

P2

我们可以从之前的进度,或者edX 的 tuition-graph-v3.rkt开始实现函数。

第一个就是通过学校列表得到柱状图的函数:ListOfSchool -> Image,其目的是produce bar chart showing names and tuitions of consumed schools,称该函数为chart

桩函数是:(define (chart los) (square 0 "solid" "white"))

先写它的测试,先是简单的empty,再是有一个学校的情况。对于一根柱子,我们需要用到rectangle,文本则是text。文本的旋转靠rotate。在算柱子高度的时候需要考虑Y-SCALE

由于我们需要控制每个图像元素的相对方位,比如柱子整体是靠下而不是靠上的。文本也是居中向下对齐的,我们就可以使用beside/align或是overlay/align等,传入后面元素来排版。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(check-expect (chart empty) (square 0 "solid" "white"))
(check-expect (chart (cons (make-school "S1" 8000) empty))
(beside/align "bottom"
(overlay/align "center" "bottom"
(rotate 90 (text "S1" FONT-SIZE FONT-COLOR))
(rectangle BAR-WIDTH (* 8000 Y-SCALE) "outline" "black")
(rectangle BAR-WIDTH (* 8000 Y-SCALE) "solid" BAR-COLOR))
(square 0 "solid" "white")))

(check-expect (chart (cons (make-school "S2" 12000) (cons (make-school "S1" 8000) empty)))
(beside/align "bottom"
(overlay/align "center" "bottom"
(rotate 90 (text "S2" FONT-SIZE FONT-COLOR))
(rectangle BAR-WIDTH (* 12000 Y-SCALE) "outline" "black")
(rectangle BAR-WIDTH (* 12000 Y-SCALE) "solid" BAR-COLOR))
(overlay/align "center" "bottom"
(rotate 90 (text "S1" FONT-SIZE FONT-COLOR))
(rectangle BAR-WIDTH (* 8000 Y-SCALE) "outline" "black")
(rectangle BAR-WIDTH (* 8000 Y-SCALE) "solid" BAR-COLOR))
(square 0 "solid" "white")))
(define (chart los) (square 0 "solid" "white"))
运行后测试窗口
运行后测试窗口

P3

最后就是chart的实现了,结合之前的经验,我们可以先按照模板改成这样:

1
2
3
4
5
6
(define (chart los)
(cond [(empty? los) (square 0 "solid" "white")]
[else
(beside/align "bottom"
(make-bar (first los))
(chart (rest los)))]))

其中,beside/align可以将我们发现的每个柱子挨个排着,同时出于封装角度考虑,里面我们也将要实现make-bar函数来将单个柱子绘制出来贴上去。

make-bar的签名自然就是School -> Image,目的是produce the bar for a single school in the bar chart。测试就是尝试绘制S1

1
2
3
4
5
(check-expect (make-bar (make-school "S1" 8000))
(overlay/align "center" "bottom"
(rotate 90 (text "S1" FONT-SIZE FONT-COLOR))
(rectangle BAR-WIDTH (* 8000 Y-SCALE) "outline" "black")
(rectangle BAR-WIDTH (* 8000 Y-SCALE) "solid" BAR-COLOR)))

桩函数是;(define (make-bar s) (square 0 "solid" "white")) ; stub

可以根据测试,把函数体实现了:

1
2
3
4
5
(define (make-bar s)
(overlay/align "center" "bottom"
(rotate 90 (text (school-name s) FONT-SIZE FONT-COLOR))
(rectangle BAR-WIDTH (* (school-tuition s) Y-SCALE) "outline" "black")
(rectangle BAR-WIDTH (* (school-tuition s) Y-SCALE) "solid" BAR-COLOR)))

最后运行,在交互区先输入(chart LOS1)回车,再输出(chart LOS2)回车,就能得到一个有三个School的柱状图。

函数部分代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
(check-expect (chart empty) (square 0 "solid" "white"))
(check-expect (chart (cons (make-school "S1" 8000) empty))
(beside/align "bottom"
(overlay/align "center" "bottom"
(rotate 90 (text "S1" FONT-SIZE FONT-COLOR))
(rectangle BAR-WIDTH (* 8000 Y-SCALE) "outline" "black")
(rectangle BAR-WIDTH (* 8000 Y-SCALE) "solid" BAR-COLOR))
(square 0 "solid" "white")))

(check-expect (chart (cons (make-school "S2" 12000) (cons (make-school "S1" 8000) empty)))
(beside/align "bottom"
(overlay/align "center" "bottom"
(rotate 90 (text "S2" FONT-SIZE FONT-COLOR))
(rectangle BAR-WIDTH (* 12000 Y-SCALE) "outline" "black")
(rectangle BAR-WIDTH (* 12000 Y-SCALE) "solid" BAR-COLOR))
(overlay/align "center" "bottom"
(rotate 90 (text "S1" FONT-SIZE FONT-COLOR))
(rectangle BAR-WIDTH (* 8000 Y-SCALE) "outline" "black")
(rectangle BAR-WIDTH (* 8000 Y-SCALE) "solid" BAR-COLOR))
(square 0 "solid" "white")))

;(define (chart los) (square 0 "solid" "white")) ; stub
(define (chart los)
(cond [(empty? los) (square 0 "solid" "white")]
[else
(beside/align "bottom"
(make-bar (first los))
(chart (rest los)))]))

;; School -> Image
;; produce the bar for a single school in the bar chart
(check-expect (make-bar (make-school "S1" 8000))
(overlay/align "center" "bottom"
(rotate 90 (text "S1" FONT-SIZE FONT-COLOR))
(rectangle BAR-WIDTH (* 8000 Y-SCALE) "outline" "black")
(rectangle BAR-WIDTH (* 8000 Y-SCALE) "solid" BAR-COLOR)))

(define (make-bar s)
(overlay/align "center" "bottom"
(rotate 90 (text (school-name s) FONT-SIZE FONT-COLOR))
(rectangle BAR-WIDTH (* (school-tuition s) Y-SCALE) "outline" "black")
(rectangle BAR-WIDTH (* (school-tuition s) Y-SCALE) "solid" BAR-COLOR)))

Practice Problems

这一章的 Recommended Problems:

Reference P1 - Alternative Tuition Graph 这道题是上述的简单变种,有兴趣可以自行尝试

Reference P2 - Spinning Bears 题解

预计耗时:100 min / 困难

这道题确实很难,但我们可以将这个大问题分而治之。看完题目后,我们无非需要做这些事:

  • 窗口属性、空白背景和熊的属性这些基本信息
  • 一只熊的数据定义,以及一堆熊的列表
  • 含有big-bangmain函数,需要on-tickto-draw,也需要响应鼠标事件的handle-mouse
  • big-bang对应的三个函数

我们可以挨个处理。

首先是一些常量,这道题本质上是个 HtDW 设计题,窗口宽高和空白背景是必须的。同时熊的图像定义和旋转速度也是要的。

1
2
3
4
5
6
7
8
(define WIDTH 600) ; width of the scene
(define HEIGHT 700) ; height of the scene

(define SPEED 3) ; speed of rotation

(define MTS (empty-scene WIDTH HEIGHT)) ; the empty scene

(define BEAR-IMG <熊的图像>)

接下来就是数据定义部分。可能一开始思考的时候觉得熊就是一只单纯的熊,但实际上我们需要记录每只熊的位置和方向信息。

这是因为题目需要我们达到:每点击窗口的某个地方,就在鼠标落下的位置出现一只一直旋转的熊。

那么这个bear就存在x坐标y坐标角度,它们都是有对应范围的。考虑到鼠标的点击位置并不一定是整数,而角度是保证的,我们可以总结如下:

1
2
3
4
5
6
(define-struct bear (x y r))
;; Bear is (make-bear Number[0,WIDTH] Number[0,HEIGHT] Integer)
;; interp. (make-bear x y r) is the state of a bear, where
;; x is the x coordinate in pixels,
;; y is the y coordinate in pixels, and
;; r is the angle of rotation in degrees

与此同时写上它的例子:

1
2
(define B1 (make-bear 0 0 0)) ; bear in the upper left corner
(define B2 (make-bear (/ WIDTH 2) (/ HEIGHT 2) 90)) ; sideways bear in the middle

作为一个结构,我们需要在函数模板中提到它所有的字段:

1
2
3
4
5
6
7
8
#;
(define (fn-for-bear b)
(... (bear-x b) ; Number[0,WIDTH]
(bear-y b) ; Number[0,HEIGHT]
(bear-r b))) ; Integer

;; Template Rules Used:
;; - compound: 3 fields

以上就是对一只熊的定义,接下来就是一堆熊,称其为ListOfBear

回忆本章的定义过程,可以照样子写出如下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
;; ListOfBear is one of:
;; - empty
;; - (cons Bear ListOfBear)
(define LB0 empty)
(define LB1 (cons B1 empty))
(define LB2 (cons B1 (cons B2 empty)))

#;
(define (fn-for-lob lob)
(cond [(empty? lob) (...)]
[else
(... (fn-for-bear (first lob))
(fn-for-lob (rest lob)))]))

;; Template Rules Used:
;; - one of: 2 cases
;; - atomic distinct: empty
;; - compound: 2 fields
;; - reference: (first lob) is Bear
;; - self-reference: (rest lob) is ListOfBear

数据都准备好了,就剩下处理它们的函数了。首先是main

1
2
3
4
5
6
7
8
;; ListOfBear -> ListOfBear
;; start the world with (main empty)
;;
(define (main lob)
(big-bang lob ; ListOfBear
(on-tick spin-bears) ; ListOfBear -> ListOfBear
(to-draw render-bears) ; ListOfBear -> Image
(on-mouse handle-mouse))) ; ListOfBear Integer Integer MouseEvent -> ListOfBear

ps: 有关on-mouse的参数可在 Help Desk 寻找

第一个就是处理每只熊旋转的函数,即spin-bears。它的职责很简单,就是让熊列表中的每一项转一下,测试如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
;; ListOfBear -> ListOfBear
;; spin all of the bears forward by SPEED degrees

(check-expect (spin-bears empty) empty)
(check-expect (spin-bears
(cons (make-bear 0 0 0) empty))
(cons (make-bear 0 0 (+ 0 SPEED)) empty))
(check-expect (spin-bears
(cons (make-bear 0 0 0)
(cons (make-bear (/ WIDTH 2) (/ HEIGHT 2) 90)
empty)))
(cons (make-bear 0 0 (+ 0 SPEED))
(cons (make-bear (/ WIDTH 2) (/ HEIGHT 2) (+ 90 SPEED)) empty)))

桩函数为;(define (spin-bears lob) empty)

ListOfBear的函数模板复制过来,改名为spin-bears。回顾这个函数的签名ListOfBear -> ListOfBear,这个函数最终产出的东西也得是熊列表。这就意味着我们在遍历这个列表的同时,要顺便修改其中每一项的角度。这里我们将修改角度交给封装后的函数spin-bear,这样就简洁一些:

1
2
3
4
5
6
7
;; Took template from ListOfBear

(define (spin-bears lob)
(cond [(empty? lob) empty]
[else
(cons (spin-bear (first lob))
(spin-bears (rest lob)))]))

对于修改一只熊的朝向,实现方式就是创建一只位置一样但是角度偏向的熊,其签名是Bear -> Bear

1
2
3
4
5
6
7
8
9
10
11
12
13
14
;; Bear -> Bear
;; spin a bear forward by SPEED degrees

(check-expect (spin-bear (make-bear 0 0 0)) (make-bear 0 0 (+ 0 SPEED)))
(check-expect (spin-bear (make-bear (/ WIDTH 2) (/ HEIGHT 2) 90))
(make-bear (/ WIDTH 2) (/ HEIGHT 2) (+ 90 SPEED)))

;(define (spin-bear b) b)

;; Took template from Bear
(define (spin-bear b)
(make-bear (bear-x b)
(bear-y b)
(+ (bear-r b) SPEED)))

运算的事情处理完了,第二件事就是将转好的熊放到场景内,即render-bears函数。和spin-bears一样,我们可以让显示每只熊的详细操作封装render-bear-on函数,这个函数也会递归着显示每只熊:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
;; ListOfBear -> Image
;; render the bears onto the empty scene

(check-expect (render-bears empty) MTS)
(check-expect (render-bears (cons (make-bear 0 0 0) empty))
(place-image (rotate 0 BEAR-IMG) 0 0 MTS))
(check-expect (render-bears
(cons (make-bear 0 0 0)
(cons (make-bear (/ WIDTH 2) (/ HEIGHT 2) 90)
empty)))
(place-image (rotate 0 BEAR-IMG) 0 0
(place-image (rotate 90 BEAR-IMG) (/ WIDTH 2) (/ HEIGHT 2)
MTS)))


;(define (render-bears lob) MTS)

;; Took Template from ListOfBear

(define (render-bears lob)
(cond [(empty? lob) MTS]
[else
(render-bear-on (first lob) (render-bears (rest lob)))]))

对于显示每只熊,也是用place-image,但需要注意的是,熊的角度有可能超过360度,所以我们需要用modulo来处理一下:

1
2
3
4
5
6
7
8
9
10
11
12
;; Bear Image -> Image
;; render an image of the bear on the given image

(check-expect (render-bear-on (make-bear 0 0 0) MTS) (place-image (rotate 0 BEAR-IMG) 0 0 MTS))
(check-expect (render-bear-on (make-bear (/ WIDTH 2) (/ HEIGHT 2) 90) MTS)
(place-image (rotate 90 BEAR-IMG) (/ WIDTH 2) (/ HEIGHT 2) MTS))

;(define (render-bear-on b img) MTS)

;; Took Template from Bear w/ added atomic parameter
(define (render-bear-on b img)
(place-image (rotate (modulo (bear-r b) 360) BEAR-IMG) (bear-x b) (bear-y b) img))

最后就是处理鼠标点击的函数handle-mouse,它的签名是ListOfBear Integer Integer MouseEvent -> ListOfBear,目的是On mouse-click, adds a bear with 0 rotation to the list at the x, y location

查阅文档后知道我们只需要响应"button-down"事件即可(借助(mouse=? me "button-down"))。鼠标点击时,xy是鼠标的坐标,而我们需要在这个位置添加一只熊,所以可以直接使用make-bear来创建一只熊,然后将其添加到列表中。

1
2
3
4
5
6
7
8
9
10
11
12
;; ListOfBear Integer Integer MouseEvent -> ListOfBear
;; On mouse-click, adds a bear with 0 rotation to the list at the x, y location
(check-expect (handle-mouse empty 5 4 "button-down") (cons (make-bear 5 4 0) empty))
(check-expect (handle-mouse empty 5 4 "move") empty)

;(define (handle-mouse lob x y mev) empty)


;; Templated according to MouseEvent large enumeration.
(define (handle-mouse lob x y mev)
(cond [(mouse=? mev "button-down") (cons (make-bear x y 0) lob)]
[else lob]))

最后运行通过,在交互区输入(main empty),然后点击窗口的任意位置,就会出现一只熊并开始旋转。

最终代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
;; Spinning Bears

;; =================
;; Constants:

(define WIDTH 600) ; width of the scene
(define HEIGHT 700) ; height of the scene

(define SPEED 3) ; speed of rotation

(define MTS (empty-scene WIDTH HEIGHT)) ; the empty scene

(define BEAR-IMG .)

;; =================
;; Data definitions:

(define-struct bear (x y r))
;; Bear is (make-bear Number[0,WIDTH] Number[0,HEIGHT] Integer)
;; interp. (make-bear x y r) is the state of a bear, where
;; x is the x coordinate in pixels,
;; y is the y coordinate in pixels, and
;; r is the angle of rotation in degrees

(define B1 (make-bear 0 0 0)) ; bear in the upper left corner
(define B2 (make-bear (/ WIDTH 2) (/ HEIGHT 2) 90)) ; sideways bear in the middle

#;
(define (fn-for-bear b)
(... (bear-x b) ; Number[0,WIDTH]
(bear-y b) ; Number[0,HEIGHT]
(bear-r b))) ; Integer

;; Template Rules Used:
;; - compound: 3 fields


;; ListOfBear is one of:
;; - empty
;; - (cons Bear ListOfBear)
(define LB0 empty)
(define LB1 (cons B1 empty))
(define LB2 (cons B1 (cons B2 empty)))

#;
(define (fn-for-lob lob)
(cond [(empty? lob) (...)]
[else
(... (fn-for-bear (first lob))
(fn-for-lob (rest lob)))]))

;; Template Rules Used:
;; - one of: 2 cases
;; - atomic distinct: empty
;; - compound: 2 fields
;; - reference: (first lob) is Bear
;; - self-reference: (rest lob) is ListOfBear

;; =================
;; Functions:

;; ListOfBear -> ListOfBear
;; start the world with (main empty)
;;
(define (main lob)
(big-bang lob ; ListOfBear
(on-tick spin-bears) ; ListOfBear -> ListOfBear
(to-draw render-bears) ; ListOfBear -> Image
(on-mouse handle-mouse))) ; ListOfBear Integer Integer MouseEvent -> ListOfBear

;; ListOfBear -> ListOfBear
;; spin all of the bears forward by SPEED degrees

(check-expect (spin-bears empty) empty)
(check-expect (spin-bears
(cons (make-bear 0 0 0) empty))
(cons (make-bear 0 0 (+ 0 SPEED)) empty))
(check-expect (spin-bears
(cons (make-bear 0 0 0)
(cons (make-bear (/ WIDTH 2) (/ HEIGHT 2) 90)
empty)))
(cons (make-bear 0 0 (+ 0 SPEED))
(cons (make-bear (/ WIDTH 2) (/ HEIGHT 2) (+ 90 SPEED)) empty)))

;(define (spin-bears lob) empty)

;; Took template from ListOfBear

(define (spin-bears lob)
(cond [(empty? lob) empty]
[else
(cons (spin-bear (first lob))
(spin-bears (rest lob)))]))


;; Bear -> Bear
;; spin a bear forward by SPEED degrees

(check-expect (spin-bear (make-bear 0 0 0)) (make-bear 0 0 (+ 0 SPEED)))
(check-expect (spin-bear (make-bear (/ WIDTH 2) (/ HEIGHT 2) 90))
(make-bear (/ WIDTH 2) (/ HEIGHT 2) (+ 90 SPEED)))

;(define (spin-bear b) b)

;; Took template from Bear
(define (spin-bear b)
(make-bear (bear-x b)
(bear-y b)
(+ (bear-r b) SPEED)))


;; ListOfBear -> Image
;; render the bears onto the empty scene

(check-expect (render-bears empty) MTS)
(check-expect (render-bears (cons (make-bear 0 0 0) empty))
(place-image (rotate 0 BEAR-IMG) 0 0 MTS))
(check-expect (render-bears
(cons (make-bear 0 0 0)
(cons (make-bear (/ WIDTH 2) (/ HEIGHT 2) 90)
empty)))
(place-image (rotate 0 BEAR-IMG) 0 0
(place-image (rotate 90 BEAR-IMG) (/ WIDTH 2) (/ HEIGHT 2)
MTS)))


;(define (render-bears lob) MTS)

;; Took Template from ListOfBear

(define (render-bears lob)
(cond [(empty? lob) MTS]
[else
(render-bear-on (first lob) (render-bears (rest lob)))]))


;; Bear Image -> Image
;; render an image of the bear on the given image

(check-expect (render-bear-on (make-bear 0 0 0) MTS) (place-image (rotate 0 BEAR-IMG) 0 0 MTS))
(check-expect (render-bear-on (make-bear (/ WIDTH 2) (/ HEIGHT 2) 90) MTS)
(place-image (rotate 90 BEAR-IMG) (/ WIDTH 2) (/ HEIGHT 2) MTS))

;(define (render-bear-on b img) MTS)

;; Took Template from Bear w/ added atomic parameter
(define (render-bear-on b img)
(place-image (rotate (modulo (bear-r b) 360) BEAR-IMG) (bear-x b) (bear-y b) img))



;; ListOfBear Integer Integer MouseEvent -> ListOfBear
;; On mouse-click, adds a bear with 0 rotation to the list at the x, y location
(check-expect (handle-mouse empty 5 4 "button-down") (cons (make-bear 5 4 0) empty))
(check-expect (handle-mouse empty 5 4 "move") empty)

;(define (handle-mouse lob x y mev) empty)


;; Templated according to MouseEvent large enumeration.
(define (handle-mouse lob x y mev)
(cond [(mouse=? mev "button-down") (cons (make-bear x y 0) lob)]
[else lob]))