Scheme
SICP

オンラインSICP読書女子会 #9(1.3.2 ~ 1.3.3 lambdaとletと仲良し) まとめ

More than 1 year has passed since last update.

1.3.2

練習問題1.34

f(x) = x(2)
のとき
f(f) は、 f(f) = f(2) = 2(2)

2は引数を取る手続きではないためエラー

(define (f g) (g 2))
(print "1.34 sample:"
       (f (lambda (x) (* x x)))) ;; 4

(f f) ;; *** ERROR: invalid application: (2 2)

疑問

defineとletの使い分け方。

define は内部手続きの定義 に限定して使うようにしています。

注釈54:
 内部定義を十分に理解し、望むとおりの意味をプログラムに確実に持たせられるようになるには、
 この章で紹介したものよりも精巧な評価プロセスのモデルが必要です。
 しかし、手続きの内部定義ではこの微妙な問題は起こりません。
 4.1.6 節で評価についてより深く学んだのちに、この問題に戻ってきます。

というようにあるけど、まだよくわからない。
そのほうが設計しやすいよーってこと? また4章でじっくりやるっぽい。

@hio-harp: 定数はletでかいて関数をdefineでかいたりする

1.3.3

関数の不動点 f(x) = xを満たす時, xを不動点と呼ぶ
不動点 - Wikipedia

練習問題1.35

黄金比 φ(1.2.2 節) が x → 1 + 1/x という変形の不動点であることを示し、そのことを利用して φ を fixed-point 手 続きによって求めよ。

黄金比は

φ^2 = φ + 1

黄金比に

x \mapsto 1 + \frac{1}{x}

という不動点があることを示す。

不動点とは、以下の式が成り立つ x
math
f(x) = x

xが0の時、x^2 = x + 1 は成り立たない。

\begin{align}

φ^2 &= φ + 1 \\
φ^2 - φ - 1 &= 0 \\ 
φ - 1 - \frac{1}{φ} &= 0 (φ \neq 0)\\ 

\end{align}

ここまで描いて、「で?」ってなってる。示すのよくわかない・・・。

;; 1.35
(define tolerance 0.00001)
(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))

(fixed-point (lambda (x) (+ 1 (/ 1.0 x)) ) 1) ;;φ = 1.6180327868

練習問題1.36

x^x = 1000

のxを求めよ

;; ふつうver
(define (fixed-point f first-guess)
  (define tolerance 0.00001)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define cnt 0)

  (define (try guess counter)
    (print counter ":" guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
      next
      (try next (+ counter 1)))))

  (try first-guess 0))

(define point (fixed-point (lambda (x) (/ (log 1000) (log x))) 2))
;; 1:9.965784284662087
;; 2:3.004472209841214
;; 3:6.279195757507157
;; 4:3.759850702401539
;; 5:5.215843784925895
;; 6:4.182207192401397
;; 7:4.8277650983445906
;; 8:4.387593384662677
;; 9:4.671250085763899
;; 10:4.481403616895052
;; 11:4.6053657460929
;; 12:4.5230849678718865
;; 13:4.577114682047341
;; 14:4.541382480151454
;; 15:4.564903245230833
;; 16:4.549372679303342
;; 17:4.559606491913287
;; 18:4.552853875788271
;; 19:4.557305529748263
;; 20:4.554369064436181
;; 21:4.556305311532999
;; 22:4.555028263573554
;; 23:4.555870396702851
;; 24:4.555315001192079
;; 25:4.5556812635433275
;; 26:4.555439715736846
;; 27:4.555599009998291
;; 28:4.555493957531389
;; 29:4.555563237292884
;; 30:4.555517548417651
;; 31:4.555547679306398
;; 32:4.555527808516254
;; 33:4.555540912917957
;; 4.555527808516254

;; 4.555527808516254 ** 4.555527808516254 = 999.9801294506152



;; 平均緩和法ver
(define (fixed-point f first-guess)
  (define tolerance 0.00001)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))

  (define (average v1 v2) (/(+ v1 v2) 2))

  (define (try guess counter)
    (print counter ":" guess)
    (let ((next (average guess (f guess))))
      (if (close-enough? guess next)
      next
      (try next (+ counter 1)))))

  (try first-guess 0))

(define point (fixed-point (lambda (x) (/ (log 1000) (log x))) 2))
;; 0:2
;; 1:5.9828921423310435
;; 2:4.922168721308343
;; 3:4.628224318195455
;; 4:4.568346513136242
;; 5:4.5577305909237005
;; 6:4.555909809045131
;; 7:4.555599411610624
;; 8:4.5555465521473675
;; 試行回数めっちゃ減った!!!!!!!

平均緩和法すごい・・・。
宿題:なんでこんなに減るのかちゃんと調べる