SchemeとRubyで高階関数を学ぼう ~その2~

前回に引き続き「[rakuten:book:10825992:title]」を使って
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を定義し抽象化する
これを用いて例えば
方程式の解が得られる

 (fixed_point (lambda (y) (+ (sin y) (cos y)))
 		 1.0)
 1.25873159629712

平方根の計算は不動点探索の問題に置き換えられる
つまりxの平方根の計算は = 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))))

例えばこれにをとする手続きsquareを渡すと
との平均を値とする手続きを返す
だから例えばこの返された手続きに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

[rakuten:book:10825992:detail]
(追記:2009/2/1）タイトルを「RubyでSchemeの高階関数を学ぼう~その2~」から「SchemeでRubyの高階関数を学ぼう~その2~」に変えました
(追記:2009/2/5)　タイトルを「SchemeでRubyの高階関数を学ぼう~その2~」から「SchemeとRubyで高階関数を学ぼう~その2~」に変えました