我们遇到的问题规模在扩大，但难度其实并没有增加很多。在遇到复杂问题的时候，我们需要学会拆开函数，设计一些辅助函数 (Helper functions) 来帮助我们完成任务。

在之前，我们对于很复杂的设计问题，总是会自然地拆开一个函数用于简化代码编写。实际上，分而治之地解决一个大问题是一种非常重要的编程技巧。

学习目标

  • 引用其他非原始数据定义（这将包含在模板中）
  • 能够组合函数
  • 处理知识域 (knowledge domain) 迁移
  • 操作任意规模的数据
以下内容涉及到的edX链接均不保证可访问性

Function Composition

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

arrange-image-starter.rkt
arrange-image-starter.rkt

这道题首先让我们设计一个数据定义，表示任意数量的图片。

(A) Design a data definition to represent an arbitrary number of images.

直接上手，从上一章对列表的数据定义开始：

1
2
3
4
5
6
;; ListOfImage is one of:
;;   - empty
;;   - (cons Image ListOfImage)
;; interp. An arbitrary number of images
(define LOI1 empty)
(define LOI2 (cons (rectangle 10 20 "solid" "blue") (cons (rectangle 20 30 "solid" "red") empty)))

函数模板也和之前一样，处理空和非空两种情况，非空的情况需要处理first和rest递归：

1
2
3
4
5
6
#;
(define (fn-for-loi loi)
    (cond [(empty? loi) (...)]
          [else
           (... (first loi)
                (fn-for-loi (rest loi)))]))

接下来就是第二个问题，设计一个叫做arrange-images的函数，接受一个ListOfImage，返回一个新的Image，把所有图片从左到右排列起来，且图片本身的大小逐渐增加。

(B) Design a function called arrange-images that consumes an arbitrary number of images and lays them out left-to-right in increasing order of size.

函数的签名、目的和例子：

1
2
3
4
5
;; ListOfImage -> Image
;; lay out images left to right in increasing order of size
(check-expect (arrange-images empty) BLANK)
(check-expect (arrange-images (cons (rectangle 10 20 "solid" "blue") (cons (rectangle 20 30 "solid" "red") empty))) 
                (beside (rectangle 10 20 "solid" "blue") (rectangle 20 30 "solid" "red") blank))

桩函数：;(define (arrange-images loi) BLANK) ; stub

也许你会觉得我们接下来会将函数模板复制过来直接写，但实际上我们需要提前思考一下这个问题该如何拆解，每涉及到对一种数据的操作，我们最好都需要设计一个函数来处理它：

  • 一个用来排序图片大小的函数
  • 一个用来将图片从左到右排列的函数

当然，arrange-images函数本身也是有内容的，就是调用上面两个函数：

1
2
(define (arrange-images loi)
  (layout-images (sort-images loi)))
graph TD;
    arrange_images(arrange-images) --> sort_images(sort-images);
    arrange_images --> layout_images(layout-images);

对于layout-images函数：

1
2
3
4
;; ListOfImage -> Image
;; place images beside each other in order of list
;; !!!
(define (layout-images loi) BLANK)

对于sort-images函数：

1
2
3
;; ListOfImage -> ListOfImage
;; sort images in increasing order of size
(define (sort-images loi) loi)

你会发现这个问题被拆成两个步骤了，虽然我们还没有实现这两个函数，但我们已经有了一个清晰的思路。

Laying Out a List of Images

如果你的进度中断了，可以下载来自edX的 arrange-images-v2.rkt 文件开始。

这一节我们会完善程序的layout-images函数，使其能够将图片从左到右排列。按照惯例，我们应当写一些测试：

1
2
3
4
5
6
7
(check-expect (layout-images empty) BLANK)
(check-expect (layout-images (cons (rectangle 10 20 "solid" "blue")
                                   (cons (rectangle 10 20 "solid" "red")
                                         empty)))
              (beside (rectangle 10 20 "solid" "blue")
                      (rectangle 10 20 "solid" "red")
                      BLANK))

上一节剩下的(define (layout-images loi) BLANK)自然变成桩函数了。然后我们复制一个模板下来，开始写函数体：

  • empty的情况当然对应的就是BLANK
  • 非空的情况需要处理first和rest递归
1
2
3
4
5
(define (layout-images loi)
  (cond [(empty? loi) BLANK]
        [else
         (beside (first loi)
                 (layout-images (rest loi)))]))

当然，运行测试后会发现和预期结果不符，图像的顺序似乎反了。

与预期相反的图像
与预期相反的图像

但还好，至少layout-images的测试通过了。

Operating on a List

如果你的进度中断了，可以下载来自edX的 arrange-images-v3.rkt 文件开始，本节将会完成sort-images函数。

这个函数的目的很简单，就是将图像按大小从小到大排序，之后交由外层的layout-images函数进行布局。测试如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
(check-expect (sort-images empty) empty)
(check-expect (sort-images (cons (rectangle 10 20 "solid" "blue")
                                 (cons (rectangle 20 30 "solid" "red")
                                       empty)))
              (cons (rectangle 10 20 "solid" "blue")
                    (cons (rectangle 20 30 "solid" "red")
                          empty)))
(check-expect (sort-images (cons (rectangle 20 30 "solid" "red")
                                  (cons (rectangle 10 20 "solid" "blue")
                                        empty)))
              (cons (rectangle 10 20 "solid" "blue")
                    (cons (rectangle 20 30 "solid" "red")
                          empty)))

(check-expect (sort-images (cons (rectangle 30 40 "solid" "green")
                                  (cons (rectangle 10 20 "solid" "blue")
                                        (cons (rectangle 10 20 "solid" "blue")
                                              empty))))
              (cons (rectangle 30 40 "solid" "green")
                    (cons (rectangle 10 20 "solid" "blue")
                          (cons (rectangle 20 30 "solid" "red")
                                empty))))

将之前的(define (sort-images loi) loi)注释上，复制函数模板，开始编写函数体。

  • empty自然就是empty
  • 非空的时候，我们需要将剩余的图像进行排序，然后将它们递归地放到第一位。我们该如何达到这一点呢？

出于封装的角度考虑，我们可以实现一个insert函数，传入一个图像和一个已排序的图像列表，然后将图像插入到合适的位置返回：

1
2
3
4
5
;; Image ListOfImage -> ListOfImage
;; insert img in proper place in 1st (in increasing order of size)
;; ASSUME: 1st is already sorted
;; !!!
(define (insert img 1st) 1st)
graph TD
  A(arrange-images) --> B(sort-images)
  A --> C(layout-images)
  B --> D(insert)

Domain Knowledge Shift

如果你的进度中断了，可以下载来自edX的 arrange-images-v4.rkt 文件开始。

回顾整个代码，我们会发现测试部分有很多地方是重复的，我们可以通过define常量来将它们抽出来，放在Constants的位置：

1
2
3
4
;; for testing:
(define I1 (rectangle 10 20 "solid" "blue"))
(define I2 (rectangle 20 30 "solid" "red"))
(define I3 (rectangle 30 40 "solid" "green"))

之后，使用之前所学的全局替换将其他地方的测试用例中的图像替换为这些常量。

这样，我们的测试用例就能更轻易地维护，如需修改测试，大多数时候只需要修改常量的定义即可。

回到我们上一节没实现完的insert函数，我们可以开始更方便地写测试了：

1
2
3
4
(check-expect (insert I1 empty) (cons I1 empty))
(check-expect (insert I1 (cons I2 (cons I3 empty))) (cons I1 (cons I2 (cons I3 empty))))
(check-expect (insert I2 (cons I1 (cons I3 empty))) (cons I1 (cons I2 (cons I3 empty))))
(check-expect (insert I3 (cons I1 (cons I2 empty))) (cons I1 (cons I2 (cons I3 empty))))

然后开始写函数体，可以从数据定义那复制过来。

  • 如果loi是empty，考虑到返回类型是ListOfImage，需要返回的其实是(cons img empty)而不是empty，不然会漏掉img
  • 如果loi是非空的，我们需要将img与first进行比较，然后决定将img放在first之前还是之后。

比如说：

  • 对于(insert I1 (cons I2 (cons I3 empty)))测试：
    • I1比I2小，就将I1放在I2之前。
  • 对于(insert I2 (cons I1 (cons I3 empty)))测试：
    • I2比I1大，就将I2放在I1之后。
  • 对于(insert I3 (cons I1 (cons I2 empty)))测试：
    • I3比I2大，就将I3放在I2之后。

那么思路就比较清晰了，在loi非空的情况下，如果img比first大，那么就将img放在first之后，递归地将img插入到rest中；如果img比first小，那么就将img放在first之前，返回一个新的列表。

当然，我们也需要一个函数来帮我们判断图像大小，暂且称为larger?：

1
2
3
4
5
6
7
8
(define (insert img loi)
  (cond [(empty? loi) (cons img empty)]
        [else
         (if (larger? img (first loi))
             (cons (first loi)
                   (insert img
                           (rest loi)))
             (cons img loi))]))
graph TD
  A(arrange-images) --> B(sort-images)
  A --> C(layout-images)
  B --> D(insert)
  D --> E(larger?)

The Last Helper

如果你的进度中断了，可以下载来自edX的 arrange-images-v5.rkt 文件开始。

书接上回，larger?函数需要接受两个图像，做一些与它们宽高相关的运算之后返回一个布尔值。测试如下：

1
2
3
4
5
(check-expect (larger? (rectangle 3 4 "solid" "red") (rectangle 2 6 "solid" "red")) false)
(check-expect (larger? (rectangle 5 4 "solid" "red") (rectangle 2 6 "solid" "red")) true)
(check-expect (larger? (rectangle 3 5 "solid" "red") (rectangle 2 6 "solid" "red")) true)
(check-expect (larger? (rectangle 3 4 "solid" "red") (rectangle 5 6 "solid" "red")) false)
(check-expect (larger? (rectangle 3 4 "solid" "red") (rectangle 2 7 "solid" "red")) false)

函数体很简单，比较两个图像的面积即可：

1
2
3
(define (larger? img1 img2)
  (> (* (image-width img1) (image-height img1))
     (* (image-width img2) (image-height img2))))

运行后，所有的测试都通过了，我们完成了这道题。

Practice Problems

这一章的 Recommended Problems:

Helpers P2 - Making Rain Filtered 题解

预计耗时：120 min / 困难

这道题让我们在一个天蓝色背景的窗口里显示多个下降的雨滴，同时鼠标点击的地方也能出现一个新的雨滴，需要注意的是，落出窗口外的雨滴不应当在之后的事件循环中被处理到。常数、数据定义等部分已经帮我们写好了，我们只需要处理big-bang即可。

此处的big-bang包含三个事件处理器：

  • on-tick：每隔一段时间更新雨滴的位置
  • on-mouse：鼠标点击时生成新的雨滴
  • to-draw：负责绘制所有雨滴

首先是on-tick的next-drops函数，它的测试如下：

1
2
3
4
5
6
(check-expect (next-drops empty) empty)
(check-expect (next-drops (cons (make-drop 3 4)
                                (cons (make-drop 90 HEIGHT)
                                      empty)))
              (cons (make-drop 3 5)
                    empty))

由于计算雨滴落下需要注意雨滴是否还在窗口内，我们需要将实际运算函数上套一个检测函数，比如：

1
2
(define (next-drops lod)
  (onscreen-only (tick-drops lod)))

对于tick-drops函数，我们需要更新每个水滴的位置 —— 给它的y坐标加上SPEED即可。由于这个函数同样需要返回ListOfDrop，所以在递归调用的同时需要用cons存住：

1
2
3
4
5
(define (tick-drops lod)
  (cond [(empty? lod) empty]
        [else 
         (cons (make-drop (drop-x (first lod)) (+ SPEED (drop-y (first lod))))
               (tick-drops (rest lod)))]))

这样下落的效果就做好了，接下来我们需要处理屏幕外的水滴。由于其本质是筛选的过程，所以在递归过程中，每个first都应该去检查其y坐标是否还在窗口内，如果在就算上，否则就带着剩下的lod递归：

1
2
3
4
5
6
(define (onscreen-only lod)
  (cond [(empty? lod) empty]
        [else
         (if (<= 0 (drop-y (first lod)) HEIGHT)
             (cons (first lod) (onscreen-only (rest lod)))
             (onscreen-only (rest lod)))]))

接下来实现render-drops，渲染最复杂的就是我们如何在渲染first的同时又能让剩下的接着递归渲染。我们可以写一个place-drop函数来帮我们做到这一点：

1
2
3
4
5
(define (render-drops lod)
  (cond [(empty? lod) MTS]
        [else 
         (place-drop (first lod)
                     (render-drops (rest lod)))]))

place-drop接受当前水滴的数据和剩下待处理的水滴。第二个参数让渲染变得可以递归，每次渲染后都能调回render-drops进行处理：

1
2
(define (place-drop d img)
  (place-image DROP (drop-x d) (drop-y d) img))

最后就是鼠标点击事件的响应函数handle-mouse了，它本身能传入当前lod，鼠标点击的坐标和行为类型。我们只需要它的点击事件就行，其他的就原封不动返回原列表：

1
2
3
(define (handle-mouse lod x y mevt)
  (cond [(mouse=? mevt "button-down") (cons (make-drop x y) lod)]
        [else lod]))
参考资料
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。