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

100円〜で好評発売中！
M'ELBORNE BOOKS