[TOC=2] ## 8.1 简介 **高阶函数(Higher Order Function)**是一种以函数为参数的函数。它们都被用于**映射(mapping)**、**过滤(filtering)**、**归档(folding)**和**排序(sorting)**表。高阶函数提高了程序的模块性。编写对各种情况都适用的高阶函数与为单一情况编写递归函数相比,可以使程序更具可读性。比如说,使用一个高阶函数来实现排序可以使得我们使用不同的条件来排序,这就将排序条件和排序过程清楚地划分开来。函数`sort`具有两个参数,其一是一个待排序的表,其二是**定序(Ordering)**函数。下面展示了按照大小将一个整数表正序排序。`<`函数就是(本例中的)两数的定序函数。 ~~~ (sort '(7883 9099 6729 2828 7754 4179 5340 2644 2958 2239) <) ;⇒ (2239 2644 2828 2958 4179 5340 6729 7754 7883 9099) ~~~ 另一方面,按照每个数末两位的大小排序可以按下面的方式实现: ~~~ (sort '(7883 9099 6729 2828 7754 4179 5340 2644 2958 2239) (lambda (x y) (< (modulo x 100) (modulo y 100)))) ;⇒ (2828 6729 2239 5340 2644 7754 2958 4179 7883 9099) ~~~ 正如这里所演示的,像**快速排序(Quick Sort)**、**归并排序(Merge Sort)**等排序过程,将定序函数完全分离开来提高了代码的复用性。 在本节中,我将讲解预定义的高阶函数,然后介绍如何定义高阶函数。由于Scheme并不区别过程和其它的数据结构,因此你可以通过将函数当作参数传递轻松的定义自己的高阶函数。 实际上,Scheme中预定义函数的本质就是高阶函数,因为Scheme并没有定义块结构的语法,因此使用`lambda`表达式作为一个块。 ## 8.2 映射 映射是将同样的行为应用于表所有元素的过程。R5RS定义了两个映射过程:其一为返回转化后的表的`map`过程,另一为注重副作用的`for-each`过程。 ### 8.2.1 map `map`过程的格式如下: ~~~ (map procedure list1 list2 ...) ~~~ `procedure`是个与某个过程或`lambda`表达式相绑定的符号。作为参数的表的个数视`procedure`需要的参数而定。 例: ~~~ ; Adding each item of '(1 2 3) and '(4 5 6). (map + '(1 2 3) '(4 5 6)) ;⇒ (5 7 9) ; Squaring each item of '(1 2 3) (map (lambda (x) (* x x)) '(1 2 3)) ;⇒ (1 4 9) ~~~ ### 8.2.2 for-each `for-each`的格式与`map`一致。但`for-each`并不返回一个具体的值,只是用于副作用。 例: ~~~ (define sum 0) (for-each (lambda (x) (set! sum (+ sum x))) '(1 2 3 4)) sum ;⇒ 10 ~~~ > 练习1 > > 用`map`编写下面的函数: > > 1. 一个将表中所有元素翻倍的函数; > 2. 一个将两个表中对应位置元素相减的函数; ## 8.3 过滤 尽管过滤函数并没有在R5RS中定义,但MIT-Scheme实现提供了`keep-matching-items`和`delete-matching-item`两个函数。其它实现中应该有类似的函数。 ~~~ (keep-matching-items '(1 2 -3 -4 5) positive?) ;⇒ (1 2 5) ~~~ > 练习2 > > 编写下列函数: > > 1. **滤取(Filtering Out)**出一个表中的偶数; > 2. 滤取出不满足`10 ≤ x ≤ 100`的数; ## 8.4 归档 尽管在R5RS中没有定义归档函数,但MIT-Scheme提供了`reduce`等函数。 ~~~ (reduce + 0 '(1 2 3 4)) ;⇒ 10 (reduce + 0 '(1 2)) ;⇒ 3 (reduce + 0 '(1)) ;⇒ 1 (reduce + 0 '()) ;⇒ 0 (reduce + 0 '(foo)) ;⇒ foo (reduce list '() '(1 2 3 4)) ;⇒ (((1 2) 3) 4) ~~~ > 练习3 > > 1. 编写一个将表中所有元素平方的函数,然后求取它们的和,最后求和的平方根。 ## 8.5 排序 尽管R5RS中没有定义排序函数,但MIT-Scheme提供了`sort`(实为`merge-sort`实现)和`quick-sort`函数。 ~~~ (sort '(3 5 1 4 -1) <) ;⇒ (-1 1 3 4 5) ~~~ > 练习4 > > 编写下列函数 > > 1. 以`sin(x)`的大小升序排序; > 2. 以表长度降序排序; ## 8.6 apply函数 `apply`函数是将一个过程应用于一个表(译注:将表展开,作为过程的参数)。此函数具有任意多个参数,但首参数和末参数分别应该是一个过程和一个表。虽然乍看之下不然,但这个函数的确非常方便。 ~~~ (apply max '(1 3 2)) ;⇒ 3 (apply + 1 2 '(3 4 5)) ;⇒ 15 (apply - 100 '(5 12 17)) ;⇒ 66 ~~~ > 练习5 > > 用`apply`编写练习3中的函数。 ## 8.7 编写高阶函数 自己编写高阶函数非常容易。这里用`member-if`、`member`和`fractal`演示。 ### 8.7.1 member-if和member `member-if`函数使用一个谓词和一个表作为参数,返回一个子表,该子表的`car`部分即是原列表中首个满足该谓词的元素。`member-if`函数可以像下面这样定义: ~~~ (define (member-if proc ls) (cond ((null? ls) #f) ((proc (car ls)) ls) (else (member-if proc (cdr ls))))) (member-if positive? '(0 -1 -2 3 5 -7)) ;⇒ (3 5 -7) ~~~ 接下来,`member`函数检查特定元素是否在表中,该函数编写如下。函数需要三个参数,其一为用于比较的函数,其二为特定项,其三为待查找表。 ~~~ (define (member proc obj ls) (cond ((null? ls) #f) ((proc obj (car ls)) ls) (else (member proc obj (cdr ls))))) (member string=? "hello" '("hi" "guys" "bye" "hello" "see you")) ;⇒ ("hello" "see you") ~~~ ### 8.7.2 不规则曲线 生成像C曲线、龙曲线等不规则曲线可以通过在两个点中插入一个点来实现 which are generated by inserting a point(s) between two points according to a positioning function can be separated into two parts: a common routine to generate fractal curves and a positioning function. 。代码实现如下: ~~~ ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; ;;; frac.scm ;;; ;;; draw fractal curves ;;; by T.Shido ;;; on August 20, 2005 ;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; 平面直角坐标系上的点通过序对来表示,其中car部分和cdr部分分别代表 ;;; x坐标和y坐标。 ;;; 函数_x和_y用来取得坐标,point用来建立一个点。 (define _x car) (define _y cdr) (define point cons) ;;; (rappend ls0 ls1) ;;; (rappend '(1 2 3) '(4 5 6)) -> (3 2 1 4 5 6) ;;; ;;; 接受两个表作为参数,将第一个表反转后与第二个表连接起来。 (define (rappend ls0 ls1) (let loop((ls0 ls0) (ls1 ls1)) (if (null? ls0) ls1 (loop (cdr ls0) (cons (car ls0) ls1))))) ;;; (devide p1 p2 r) ;;; dividing p1 and p2 internally by the ratio r. (define (divide p1 p2 r) (point (+ (* r (_x p1)) (* (- 1.0 r) (_x p2))) (+ (* r (_y p1)) (* (- 1.0 r) (_y p2))))) ;;; (print-curve points fout) ;;; 将点输出至文件。将一系列点points按一行一个点得格式输出至fout代 ;;; 表的文件 (define (print-curve points fout) (with-output-to-file fout (lambda () (for-each (lambda (p) (display (_x p)) (display " ") (display (_y p)) (newline)) points)))) ;;; (fractal proc n points fout) ;;; 创建分型图形的高阶函数。其中,proc是定位函数,n是重复次数, ;;; points是初始点构成的表,fout是输出文件的文件名。 ;;; 函数由两个叫做loop和iter的循环构成。loop对数据表做n次插入。 ;;; The iter adds new points to the data list using the positioning function. In short, fractal generates curves by repeating iter for n times. The positioning function proc takes two points as arguments and returns a list of the first point and the interpolated point. (define (fractal proc n points fout) (let loop ((i 0) (points points)) (if (= n i) (print-curve points fout) (loop (1+ i) (let iter ((points points) (acc '())) (if (null? (cdr points)) (reverse! (cons (car points) acc)) (iter (cdr points) (rappend (proc (first points) (second points)) acc))))))) 'done) ;;; (c-curve p1 p2) ;;; C-曲线的定位函数 (define (c-curve p1 p2) (let ((p3 (divide p1 p2 0.5))) (list p1 (point (+ (_x p3) (- (_y p3) (_y p2))) (+ (_y p3) (- (_x p2) (_x p3))))))) ;;; (dragon-curve p1 p2) ;;; 龙曲线的定位函数 (define dragon-curve (let ((n 0)) (lambda (p1 p2) (let ((op (if (even? n) + -)) (p3 (divide p1 p2 0.5))) (set! n (1+ n)) (list p1 (point (op (_x p3) (- (_y p3) (_y p2))) (op (_y p3) (- (_x p2) (_x p3))))))))) ;;; (koch p1 p2) ;;; Koch曲线的定位函数 (define (koch p1 p2) (let ((p3 (divide p1 p2 2/3)) (p4 (divide p1 p2 1/3)) (p5 (divide p1 p2 0.5)) (c (/ (sqrt 3) 2))) (list p1 p3 (point (- (_x p5) (* c (- (_y p4) (_y p3)))) (+ (_y p5) (* c (- (_x p4) (_x p3))))) p4))) ~~~ 下面的代码演示了如何生成分型曲线。源代码在这里。使用之前请先编译,以节省计算时间。 ~~~ (compile-file "frac.scm") (load "frac") ;; C-Curve (fractal c-curve 14 '((0 . 0) (2 . 3)) "c14.dat") ;Value: done ;; Dragon-Curve (fractal dragon-curve 14 '((0 . 0) (1 . 0)) "d14.dat") ;Value: done ;; Koch-Curve (fractal koch 5 '((0 . 0) (1 . 0)) "k5.dat") ;Value: done ~~~ X坐标和Y坐标都存储在名字形如`*.dat`的文件中。你可以使用你喜欢的制图程序来绘制。图表1-3都是用gnuplot绘制的。 > 练习 6 > > 1. 自己实现`keep-matching-items`。 > 2. 自己实现`map`。接受不止一个表作为参数可能有点困难。剩余的参数是通过带点得序对`(.)`来定义的。其`cdr`部分以表的形式传递给函数。 例: my-list `scheme (define (my-list . x) x) `多说一句,你需要`apply`函数。 ## 8.8 小结 本章中,我讲解了高阶函数。正如在生成分形图形体现的那样,高阶函数增强了模块化成都。你可以很容易地定义高阶函数。当你编写函数时,更要在乎将其实现为更抽象的高阶函数,这样可以让你的代码能够**复用(reusable)**。 在下一章节中,我会介绍IO。 ## 8.9 习题解答 ### 8.9.1 答案1 ~~~ ; 1 (define (double ls) (map (lambda (x) (* x 2)) ls)) ; 2 (define (sub ls1 ls2) (map - ls1 ls2)) ~~~ ### 8.9.2 答案2 ~~~ ; 1 (define (filter-even ls) (keep-matching-items ls even?)) ; 2 (define (filter-10-100 ls) (keep-matching-items ls (lambda (x) (<= 10 x 100)))) ~~~ ### 8.9.3 答案3 ~~~ (define (sqrt-sum-sq ls) (sqrt (reduce + 0 (map (lambda (x) (* x x)) ls)))) ~~~ ### 8.9.4 答案4 ~~~ ; 1 (define (sort-sin ls) (sort ls (lambda (x y) (< (sin x) (sin y))))) ; 2 (define (sort-length ls) (sort ls (lambda (x y) (> (length x) (length y))))) ~~~ ### 8.9.5 答案5 ~~~ (define (sqrt-sum-sq-a ls) (sqrt (apply + (map (lambda (x) (* x x)) ls)))) ~~~ ### 8.9.6 答案6 ~~~ ; 1 (define (my-keep-matching-items ls fn) (cond ((null? ls) '()) ((fn (car ls)) (cons (car ls) (my-keep-matching-items (cdr ls) fn))) (else (my-keep-matching-items (cdr ls) fn)))) ; 2 (define (my-map fun . lss) (letrec ((iter (lambda (fun lss) (if (null? lss) '() (cons (fun (car lss)) (iter fun (cdr lss)))))) (map-rec (lambda (fun lss) (if (memq '() lss) '() (cons (apply fun (iter car lss)) (map-rec fun (iter cdr lss))))))) (map-rec fun lss))) (my-map + '(1 2 3) '(10 20 30) '(100 200 300)) ;⇒ (111 222 333) ~~~