SchemeとRubyで高階関数を学ぼう ~その2~
前回に引き続き「計算機プログラムの構造と解釈」を使って SchemeとRubyで平方根の求め方と 手続きを出力とする高階手続きをまとめてみました なおSchemeのコードは本書からの抜粋で 説明は自分の要約です
Newton法を使って平方根を求める
平方根を求めるとき 通常次々と近似を求めていくNewton法を使う
xの平方根を求める場合任意の予測値yを選び yとx/yの平均を取っていくことでより良い予測値yが得られる これを繰り返し十分に良い予測値が得られたら処理を終える この手続きはSchemeでは以下のように表現できる
(define (sqrt_iter guess x)
(if (good_enough? guess x)
guess
(sqrt_iter (improve guess x)
x)))
予想値guessがgood_enough?になるまで 改善された予想値で処理が繰り返される(improve)
予想値guessを改善する手続きimproveは次のようになる
(define (improve guess x)
(average guess (/ x guess)))
(define (average x y)
(/ (+ x y) 2))
任意の許容値を決めて手続きgood_enough?を定義する ここでは予想値の二乗とxの差が0.001より小さくなるまでとする
(define (good_enough? guess x)
(< (abs (- (square guess) x)) 0.001))
(define (square x)
(* x x))
最後に最初の予想値を1として 平方根を求めるsqrt手続きを定義すれば 任意の数の平方根が得られる
(define (sqrt x)
(sqrt_iter 1.0 x))
(sqrt 9)
3.00009155413138
次に対応するRubyのコードを書いてみる 同様にNewton法により平方根を求める
def sqrt_iter(guess, x)
if good_enough?(guess, x)
guess
else
sqrt_iter(improve(guess, x), x)
end
end
improve、good_enough?メソッドは以下のようになる
def improve(guess, x)
average(guess, x/guess)
end
def average(x, y)
(x + y) / 2
end
def good_enough?(guess, x)
(square(guess) - x).abs < 0.001
end
def square(x)
x * x
end
これで平方根を求める準備が整った
def sqrt(x)
sqrt_iter(1.0, x)
end
sqrt 9 # => 3.00009155413138
Rubyはオブジェクト指向言語なので これらのメソッドを特定のオブジェクトに 結びつけたほうがRubyっぽいかもしれない ここではNumericクラスのインスタンスメソッドとして これらの手続きを定義してみる
class Numeric
def square
self**2
end
def sqrt
sqrt_iter(1.0)
end
private
def sqrt_iter(guess)
if good_enough?(guess, self)
guess
else
sqrt_iter(improve(guess))
end
end
def improve(guess)
average(guess, self/guess)
end
def average(x, y)
(x + y) / 2
end
def good_enough?(guess, x)
(guess.square - x).abs < 0.001
end
end
2.sqrt # => 1.41421568627451
2.square # => 4
sqrt,square以外のメソッドが 外から呼び出せるのは適当でないから それらのメソッドはprivateとした
不動点探索を使って平方根を求める
平方根は不動点探索を使っても求めることができる xがf(x)=xを満たすとき、xを関数fの不動点(fixed point)という 予想値からはじめて関数fを繰り返し適用することで 不動点を見つけることができる
Schemeで表現すると以下のようになる 手続きfixed_pointは入力として 関数fと最初の予想値first_guessを取る
(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))
補助手続きとしてclose_enough?,tryを定義し抽象化する これを用いて例えば 方程式 \(y=\sin y + \cos y\) の解が得られる
(fixed_point (lambda (y) (+ (sin y) (cos y)))
1.0)
1.25873159629712
平方根の計算は不動点探索の問題に置き換えられる つまりxの平方根の計算は y^2 = x なるyを探すことだから これはy=x/yと書けy -> x/yの不動点を探しているのと等価である 先のfixed_point手続きを使って平方根を求めてみよう
(define (sqrt x)
(fixed_point (lambda (y) (average y (/ x y)))
1.0))
(sqrt 3)
1.73205080756888
なおfixed_pointに渡す関数fをx/yとすると うまく収束しないのでここでは yとx/yの平均を使っている これを平均緩和法(average damping)という
同様のことをRubyでやってみる まずfixed_pointメソッドを定義する
Tolerance = 0.00001
def fixed_point(f, first_guess)
def close_enough?(v1, v2)
(v1 - v2).abs < Tolerance
end
try = lambda do |guess|
_next = f.call(guess)
if close_enough?(guess, _next)
_next
else
try.call(_next)
end
end
try.call(first_guess)
end
fixed_point(lambda{ |y| Math.sin(y) + Math.cos(y) }, 1.0) # => 1.25873159629712
Rubyではローカル変数はメソッドを透過できないので tryをメソッドではなくブロックで定義し 引数として渡される関数fが参照できるようにした
平方根を求めよう
def sqrt(x)
fixed_point(lambda { |y| average(y, x/y) }, 1.0)
end
sqrt 3 # => 1.73205080756888
fixed_pointをMathモジュールとしたほうが Rubyっぽいかもしれない
module Math
def self.fixed_point(first_guess)
@first_guess = first_guess
_next = yield(first_guess)
if close_enough?(first_guess, _next)
_next
else
self.fixed_point(_next){ yield(@first_guess) }
end
end
private
Tolerance = 0.00001
def self.close_enough?(v1, v2)
(v1 - v2).abs < Tolerance
end
end
Math.fixed_point(1.0){ |y| Math.sin(y) + Math.cos(y) } # => 1.25873159629712
class Numeric
def sqrt
Math.fixed_point(1.0) { |y| average(y, self/y) }
end
end
3.sqrt # => 1.73205080756888
手続きを返す高階手続き
平方根を求めるのに先の例では平均緩和法を使った 今度は手続きを返すSchemeの高階手続きを使って これを一般化する
次の手続きaverage_dampは引数として手続きfをとり 手続きを返す高階手続きである
(define (average_damp f)
(lambda (x) (average x (f x))))
例えばこれに x を x^2 とする手続きsquareを渡すと x と x^2 の平均を値とする手続きを返す だから例えばこの返された手続きに10を作用させると 10と100の平均が得られる
(average_damp square) 10)
55
これを用いて先の手続きsqrtを書き換える
(define (sqrt x)
(fixed_point (average_damp (lambda (y) (/ x y)))
1.0))
(sqrt 3)
1.73205080756888
;先のコード
(define (sqrt x)
(fixed_point (lambda (y) (average y (/ x y)))
1.0))
同様の高階手続きをRubyでもやってみる average_dampメソッドは以下のようになる
def average_damp(f)
lambda { |x| average(x, f.call(x)) }
end
def sqrt(x)
fixed_point(average_damp(lambda { |y| x/y }), 1.0)
end
sqrt 3 # => 1.73205080756888
average_dampはProcオブジェクトを返す
ブロックを使えば もう少しRubyらしくなる
def average_damp
lambda { |x| average(x, yield(x)) }
end
def sqrt(x)
fixed_point(average_damp{ |y| x/y }, 1.0)
end
sqrt 3 # => 1.73205080756888
さらにsqrtをNumericクラスのインスタンスメソッドにしてみる
class Numeric
def sqrt
Math.fixed_point(1.0) { |y| average_damp{ |x| self/x }.call(y) }
end
private
def average_damp
lambda { |x| average(x, yield(x)) }
end
end
3.sqrt # => 1.73205080756888
(追記:2009/2/1)タイトルを「RubyでSchemeの高階関数を学ぼう~その2~」から「SchemeでRubyの高階関数を学ぼう~その2~」に変えました (追記:2009/2/5) タイトルを「SchemeでRubyの高階関数を学ぼう~その2~」から「SchemeとRubyで高階関数を学ぼう~その2~」に変えました
blog comments powered by Disqus