用高阶函数做抽象

高阶函数是至少满足下列一个条件的函数：

• 接受一个或多个函数作为输入
• 输出一个函数

在数学中它们也叫做算子（运算符）或泛函。微积分中的导数就是常见的例子，因为它映射一个函数到另一个函数。

在无类型lambda演算，所有函数都是高阶的；在有类型lambda演算（大多数函数式编程语言都从中演化而来）中，高阶函数一般是那些函数型别包含多于一个箭头的函数。在函数式编程中，返回另一个函数的高阶函数被称为Curry化的函数。

在很多函数式编程语言中能找到的map函数是高阶函数的一个例子。它接受一个函数f作为参数，并返回接受一个列表并应用f到它的每个元素的一个函数。

抽象出求和函数

(define (sum f a b next)
  (if (> a b) 0
      (+ (f a)
         (sum f (next a) b next))))

(define (identity x) x)
(define (square x) (* x x))
(define (inc x) (+ x 1))

// 求a到b的和
(define (sum-int a b)
  (sum identity a b inc))

// 求a到b的平方和
(define (sum-squ a b)
  (sum square a b inc))

(sum-int 1 10)
(sum-squ 1 4)
// 输出
55
30

同理，可抽象出求乘积过程

// 递归
(define (product f a b next)
  (if (> a b) 1
      (* (f a)
         (product f (next a) b next))))

// 迭代
(define (pro f a b next)
  (define (iter a result)
    (if (> a b) result
        (* (f a)
           (iter (next a) result))))
  (iter a 1))

// 求a到b的积
(define (product-int a b)
  (product identity a b inc))

(define (pro-int a b)
  (pro identity a b inc))

// 求n的阶乘
(define (factorial n)
  (product identity 1 n inc))

(product-int 1 5)
(pro-int 1 5)
(factorial 6)
// 输出
120
120
720

由以上的求和、求乘积可知这两种过程有共同点，于是可再抽象成累积过程，再利用累积过程实现求和、求乘积函数

(define (ac comb null-val f a next b)
  (define (iter a result)
    (if (> a b) result
        (iter (next a)
              (comb (f a) result))))             
  (iter a null-val))

(define (sum-ac a b)
  (ac + 0 identity a inc b))

(define (pro-ac a b)
  (ac * 1 identity a inc b))

(sum-ac 1 10)
(pro-ac 1 6)
// 输出
55
720

引进一个处理被组合项的过滤器（filter）概念。
在计算过程中，只组合起由给定范围得到的项里的那些满足特定条件的项。

// 递归
(define (acc comb null-val f a b next filter)
   (if (> a b) null-val
       (let ((rest-terms (acc comb null-val f (next a) b next filter)))
         (if (filter a) (comb (f a) rest-terms)
             rest-terms))))

// 迭代
(define (accu comb null-val f a b next filter)
  (define (iter a result)
    (if (> a b) result
        (let ((rest-terms (iter (next a) result)))
          (if (filter a) (comb (f a) rest-terms)
              rest-terms))))
  (iter a null-val))

(require math)

// 求从a到b的素数之和
(define (prime-sum a b)
  (accu + 0 identity a b inc prime?))

// 求小于n的所有与n互素的正整数之乘积
(define (coprime-pro n)
  (accu * 1 identity 1 n inc (lambda (x) (coprime? x n))))

(prime-sum 1 10)
(coprime-pro 10)
// 输出
17
189

构造f的n次重复应用，将其定义为一个函数，这个函数在x的值是f(f(...(f(x))...))

(define (compose f g)
  (lambda (x) (f (g x))))

(define (repeated f n)
  (if (= n 1) f
      (compose f
               (repeated f (- n 1)))))

((repeated square 2) 5)    ; (square (square 5))
((repeated square 3) 2)    ; (square (square (square 2)))

// 输出
625
256