第6回SICP勉強会

1.3.2 lambdaを使う手続きの構築

  • 手続きを作り出す特殊形式lambda
    • 一般的にlambdaは、手続きに名前がつかない他は、defineと同様に手続きを作り出すのに使う
局所変数を作り出すlet
  • let式は基盤となるlambda作用の構文シュガーに過ぎない
  • let式で指定された変数の有効範囲はletの本体である
  • 局所変数の値を用意する式が、局所変数と同じ名前の変数に依存している時、問題となる

問題1.31

;; 問題1-31

;; a. 与えられた範囲の点での関数値の積を返すproductを用いたfactorial
(define (product term a next b)
  (if (> a b)
      1
      (* (term a)
         (product term (next a) next b))))

(define (factorial n)
  (define (inc x) (+ x 1))
  (define (identity x) x)
  (product identity 1 inc n))

(factorial 6)
;;gosh> product
;;gosh> 720

;; 普通のfactorial
(define (normal-factorial n)
  (if (= n 1)
      1
      (* n (normal-factorial (- n 1)))))

(normal-factorial 6)
;;gosh> product
;;gosh> 720

;; John Wallisの式
(define (wallis n)
  (define (square x) (* x x))
  (define (next x) (+ x 1))
  (define (term x)
    (/ (* (* x 2) (* (+ x 1) 2))
       (square (+ (* x 2) 1))))
  (product term 1.0 next n))

(wallis 100)
;;gosh> 0.7873446182921502
(wallis 1000)
;;gosh> 0.7855943412734705
(wallis 10000)
;;gosh> 0.7854177966336237
(wallis 100000)
;;gosh> 0.7854001268753947

(use math.const)
pi/4
;;gosh> pi/4
;;0.7853981633974483



;; b. aで再帰的プロセスを書いたので反復的プロセスで書く
(define (product term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (* a result))))
  (iter a 1)) ||<**問題1.32
>|schme|
;; 問題1.32

;; a. 再帰の場合のaccumulate
(define (accumulate combiner null-value term a next b)
  (if (> a b)
      null-value
      (combiner (term a)
                (accumulate combiner null-value term (next a) next b))))1

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

(accumulate * 1 identity 1 inc 5)
;; gosh> 120
;; 1 * 2 * 3 * 4 * 5 = 120
(accumulate + 0 identity 1 inc 10)
;; gosh> 55
;; 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55



;; b. 反復の場合のaccumulate
(define (accumulate combiner null-value term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (combiner result (term a)))))
  (iter a null-value))

(accumulate * 1 identity 1 inc 5)
;; gosh> 120
;; 1 * 2 * 3 * 4 * 5 = 120
(accumulate + 0 identity 1 inc 10)
;; gosh> 55 ;; 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55

問題1.33

;; 問題1.33

;; filtered-accumulate手続きの実装
(define (filtered-accumulate filter combiner null-value term a next b)
  (if (> a b)
      null-value
      (if (filter a)
          (combiner (term a)
                    (filtered-accumulate filter combiner null-value term (next a) next b))
          (filtered-accumulate filter combiner null-value term (next a) next b))))

;; ついでに反復でも実装
(define (accumulate combiner null-value term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (combiner result (term a)))))
  (iter a null-value))

(define (filtered-accumulate filter combiner null-value term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (if (filter a)
            (iter (next a) (combiner result (term a)))
            (iter (next a) result))))
  (iter a null-value))

;; 素数を判定するprime?の実装
(define (prime? n)
  (if (= n 1)
      #f
      (= n (smallest-divisor n))))

(define (smallest-divisor n)
  (find-divisor n 2))

(define (find-divisor n test-divisor)
  (cond [(> (square test-divisor) n) n]
        [(divides? test-divisor n) test-divisor]
        [else (find-divisor n (+ test-divisor 1))]))

(define (divides? a b)
  (= (remainder b a) 0))

(define (square n)
  (* n n))

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


;; a. 区間a, bの素数の二乗の和
(define (sum-of-prime a b)
  (filtered-accumulate prime? + 0 identity a inc b))

(sum-of-prime 1 10)
;; gosh> 17
;; 2 + 3 + 5 + 7 = 17


;; b. nと互いに素で、nより小さい正の整数の積
(define (product-of-gcd n)
  (define (gcd a b)
    (if (= b 0)
        a
        (gcd b (remainder a b))))
  (define (gcd-filter x)
    (= (gcd n x) 1))

  (filtered-accumulate gcd-filter * 1 identity 1 inc n))

(product-of-gcd 5)
;;gosh> 24
;; 2 * 3 * 4
(product-of-gcd 6)
;;gosh> 5
;; 6より小さくて6と互いに素な整数は5のみ
(product-of-gcd 7)
;;gosh> 720 ;; 2 * 3 * 4 * 5 * 6 = 720

問題1.34

;; 問題1.34

(define (f g)
  (g 2))

(define (square x)
  (* x x))

(f square)
;;gosh> 4
;; (f square) => (square 2)

(f (lambda (z) (* z (+ z 1))))
;;gosh> 6
;; ((lambda (z) (* z (+ z 1))) 2)
;; => 6

(f f)
;;gosh> *** ERROR: invalid application: (2 2)
;;Stack Trace:
;;_______________________________________

;; (f f)
;; => (f 2)
;; => (2 2)
;; 置き換えモデルに従うと上記のようになる。
;; 最終的に手続きでない2に引数2を与えて評価 ;; しようとしてエラーになる。

その他

  • 再帰を反復に書きなおす感じはだいぶつかめて気がする。
  • 前にやった時よりもletの概念がすっと頭に入ってきた気がする。