零基础SICP 07

零基础SICP 07

用高阶函数做抽象

沈浪熊猫儿

MathAgape

零基础SICP：第7课

用高阶函数做抽象	Formulating Abstractions with Higher-Order Procedures
在参数中传递函数值	Procedures as Arguments
用`lambda`构造匿名函数	Constructing Procedures Using `lambda`
函数作为一般性的方法	Procedures as General Methods
在函数中返回函数值	Procedures as Returned Values

编程的基本原理是对数据和计算的组合和抽象

在参数中传递函数值

Scheme]

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

Scheme]

(define (inc n) (+ n 1))

Scheme]

(define (same x) x)

Scheme]

Scheme]

(sum same 1 inc 100)

5050

Scheme]

用lambda构造匿名函数

Scheme]

(sum (lambda (x) (* x x)) 1 inc 10)

Scheme]

Scheme]

(sum (lambda (x) (* x x)) 1 (lambda (x) (+ x 2)) 10)

Scheme]

(sum (lambda (x) (* x x)) 2 (lambda (x) (+ x 2)) 10)

220

Scheme]

用let创建局部变量

Scheme]

(define (fib-once pair)
  (let ((a (first pair))
        (b (second pair)))
   (list b (+ a b))))

fib-once

Scheme]

(fib-once (fib-once (list 1 1)))

(2 3)

Scheme]

案例分析：区间折半法

实现：二分查找法

Scheme]

(define (average x y) (/ (+ x y) 2))

average

Scheme]

(define (search f neg-point pos-point)
  (let ((midpoint (average neg-point pos-point)))
    (if (close-enough? neg-point pos-point)
        midpoint
        (let ((test-value (f midpoint)))
          (cond ((positive? test-value)
                 (search f neg-point midpoint))
                ((negative? test-value)
                 (search f midpoint pos-point))
                (else midpoint))))))

search

实现：区间折半法

Scheme]

(define (close-enough? x y)
  (< (abs (- x y)) 0.001))

Scheme]

(define (half-interval-method f a b)
  (let ((a-value (f a))
        (b-value (f b)))
    (cond ((and (negative? a-value) (positive? b-value))
           (search f a b))
          ((and (negative? b-value) (positive? a-value))
           (search f b a))
          (else
           (error "Values are not of opposite sign" a b)))))

Scheme]

(half-interval-method sin 2.0 4.0)

3.14111328125

案例分析：寻找不动点

Scheme]

(define tolerance 0.00001)

Scheme]

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

Scheme]

(fixed-point cos 1.0)

Scheme]

(fixed-point (lambda (y) (+ (sin y) (cos y))) 1.0)

总结

代码即数据，数据即代码。

函数值可以像数据一样，作为参数传入函数，作为返回值从函数中传出。

define，lambda，let

(define (⟨函数名⟩ ⟨形式参数列表⟩) ⟨主体⟩)

(lambda (⟨形式参数列表⟩) ⟨主体⟩)

(let ((<变量1> <表达式1>)

(<变量2> <表达式2>)

…

(<变量n> <表达式n>))

⟨主体⟩)