1. 再帰的な考え方は難しい
どこで見たのか失念してしまったが (+_+) 、以下のような主旨を読んだ覚えがある。
構造化プログラミングでは、「順次、反復、分岐」が導入された。この内、「分岐」は「多態」に置き換えることができ、「反復」は再帰により表現することができる。「順次、反復、分岐」というプログラムの基本構造は、別の表現へと解体されていく。
当時、オブジェクト指向にベッタリだった。そのため、「多態」バンザイと思ったが、「再帰」に関しては苦手だった。最近、関数型の言語を触るようになった。「順次」は、モナドで置きかけることができるのかな？
プログラミングの本を読んでいると、
「再帰」
の考え方は重要だと述べられている。プログラミングの勉強をはじめたとき、一番最初につまずいたのが再帰だった。自分は、文系でフィーリング重視の脳みそ。再帰ほど、想像力に負荷をかけるものはない。 (@_@;)
定義しようとしているものを、定義しようとしているもので定義する
という意味も、その感覚も想像出来なかった。
再帰的に定義された関数に、実例を当てはめ、計算を順に追っていけば、確かに計算したいことが実現できていることを確認できる。しかし、計算を終えると、どこか狐につままれたような気分になるのが、再帰的な関数の定義。
自分で再帰的な関数を定義しようと思っても、考えるとっかかりがどこにあるのか分からない。突然迷路に投げだされ、どちらに行けばいいのかわからない感覚。いやむしろ、迷路の構造そのものが全く見えない。
Haskell を学んで良かったと思うことは、再帰を考えるための環境が整っていること。ループのための構文が用意されていないこと。関数定義において、引数のデータコンストラクタによるパターンマッチ (x:xs) があること。リスト操作において、関数 head , tail による再帰構造へと導く関数があること。これらにより、再帰的な考え方になじんでいく。
命令型のプログラミングだけではなく、関数型のプログラミングにも最初から親しんでおけば、再帰の考え方に抵抗を感じることがなかった。
2. for ループを再帰で置き換える
例えば、Ruby で
「数値の配列の要素を 2 倍して出力する」
場合、 for ループを使って書くと、
for i in [1,2,3,4,5] puts i * 2 end
再帰を使って定義するなら、
def rec_each(ary) return if ary.empty? puts ary[0] * 2 rec_each(ary[1..ary.size-1]) end rec_each [1,2,3,4,5]
これを書くためには、次の 2 点に意識を向ける必要がある。
- 配列を「先頭の要素と、それよりも後ろの要素」という構造として見る
- 配列の、最後の要素まで関数を適用した場合に、どうなるか？
再帰のわかりにくい理由は、コードにしたときの処理の流れと、人が頭で順次処理をしていくときの流れが、一致しないということにある。コードでは、最初に 2 番目の条件に着目しなければならない。
この2番目のことを、
「基底条件」
と言う。「再帰のときは、基底条件をまず書く」と覚えこんでおけば、コード書き出す契機と実際にはなる。
Python で同じ関数を書くなら、
def rec_each(ary):
if ary == []: return
print ary[0] * 2
rec_each(ary[1:])
rec_each([1,2,3,4,5])
シーケンス操作において、 ary[1:] のように、先頭の要素以降を取得する書き方が簡潔でいい。
- cf. 2.3.6 シーケンス型 の注釈(4)
Ruby では ary[1..ary.size-1] のように書いたが、もっと簡単に書けるのだろうか？オープンクラスを使い、定義するのがいいかな。
3. 配列に操作を適用する
上記を少し変更し、
「要素を変更した結果を、配列として返す」
には、どうすればいいだろうか。
ループを使って書くならば、
result = [] [1,2,3,4,5].each do |i| result << i * 2 end p result
ついでに map, inject を使っても書いてみる。
p [1,2,3,4,5].map{|i| i * 2}
p [1,2,3,4,5].inject([]){|x,y| x + [y*2]}
再帰で書くと、
def rec_each2(ary) return [] if ary.empty? return [ary[0] * 2] + rec_each2(ary[1..ary.size-1]) end
注意する点は、要素を 2 倍にした後、要素を[ ] で囲って配列にすること。それから、対象の配列が空の場合 [ ] を返すこと。この辺り、最初、ややこしく感じた。 (+_+)
Haskell で書くなら、
each :: (Num a) => [a] -> [a] each [] = [] each (x:xs) = x*2 : each xs main = print $ each [1,2,3,4,5]
比較してみると、Haskell で再帰を書いた場合の可読性は高い。リストが空の場合と、そうでない場合を明確に分けている。引数におけるパターンマッチでは、先頭の要素とそれ以降の要素に分ける書き方が簡潔。
Python で書くなら、
def rec_each2(ary):
if ary == []: return []
return [ary[0] * 2] + rec_each2(ary[1:])
print rec_each2([1,2,3,4,5])
4. 総計を求める
次に、配列の合計を求める。
ループを使って書くならば、
result = 0 for i in [1,2,3,4,5] result += i end puts result
inject を使えばよりシンプルに書ける。
p [1,2,3,4,5].inject{|x,y| x+y}
これを再帰で書いてみる。
def rec_sum(ary) return 0 if ary.empty? return ary[0] + rec_sum(ary[1..ary.size-1]) end
今度は、要素に対する操作ではないので、先ほどのように先頭の要素を [ ] で囲まない。
Haskell なら、
rec_sum :: (Num a) => [a] -> a rec_sum [] = 0 rec_sum (x:xs) = x + rec_sum(xs)
Prelude に sum があったので、別名にした。
Python だと、
def rec_sum(ary):
if ary == []: return 0
return ary[0] + rec_sum(ary[1:])
print rec_sum([1,2,3,4,5])
5. 総乗を求める
配列の要素をすべて掛け合わせたものを計算したい。
総乗 – Wikipedia によると、
「元の列」の `列’ の意味は、
数学において列（れつ、sequence）とは、対象あるいは事象が羅列されたものを順番に並べたものである。 (...)
列の各項が、数である列を数列、整数である列を整数列、多項式である列を多項式列といったように、「何々」の列を省略して「何々」列と呼ぶことは多い。適当な「文字」集合から作った列は文字列（string あるいは語 word）、ある空間の「点」の列を言うのであれば、点列である。
(列 (数学) – Wikipedia より)
「列 = シーケンス」ということは、Python では数学の列の概念に沿ってるということだろうか？
「文字の集合から作った列が文字列」
というのも、Python において、文字列は変更不可能なシーケンス型として扱われてことに対応する。
そういえば、 Haskell も文字列が文字のリストだった。
type String = [Char]
(Prelude より)
話を元に戻し、要素を掛け合わせたものをループを使って書くと、
ary = [1,2,3,4,5] result = ary[0] for i in ary[1...ary.length] result *= i end puts result
再帰で書くと、
def prod(ary) return 0 if ary.empty? return ary[0] if ary.size == 1 return ary[0] * prod(ary[1..ary.size-1]) end puts prod([1,2,3,4,5])
Haskell なら、
prod :: (Num a) => [a] -> a prod [] = 0 prod [x] = x prod (x:xs) = x * prod xs main = print $ prod [1,2,3,4,5]
Python なら、
def prod(ary):
if ary == []: return 0
if len(ary) == 1 : return ary[0]
return ary[0] * prod(ary[1:])
print prod([1,2,3,4,5])
6. 階乗を求める
再帰の問題でおなじみの階乗もやっておく。
階乗 – Wikipedia によると、
今度は、要素を渡すのではなくて、自然数を渡す関数とする。
def fact(n) return 1 if n == 0 return n * fact(n-1) end puts fact(5)
Haskell なら、
fact :: Int -> Int fact 0 = 1 fact x = x * fact(x-1) main = print $ fact 5
Python なら
def fact(n):
if n == 0 : return 1
return n * fact(n-1)
print fact(5)
7. これまでの計算を一般化する
総和、総乗の定義内容は、適用する演算子以外の部分はよく似ている。そこで、より一般化して、「演算子とリストを渡したら、累積的にそれを適用した結果を返す関数」を定義してみる。名前は適当に hoge とした。
hoge :: (Num a) => (a -> a -> a) -> [a] -> a hoge _ [] = 0 hoge _ [x] = x hoge f (x:xs) = x `f` (hoge f xs) main = print $ hoge (-) [1,2,3,4,5]
そういえば、これは前回やった foldl によく似ている。初期値を与えていないところが違うけれど。
Haskell だと、こういう一般化をするときに書きやすい。
Python で書くと、
def hoge(ary, f):
if ary == []: return 0
if len(ary) == 1: return ary[0]
return f(ary[0], hoge(ary[1:], f))
print hoge([1,2,3,4,5], lambda x,y: x-y)
Ruby で書くと、
def hoge(ary, &f)
return 0 if ary.empty?
return ary[0] if ary.size == 1
return f.call(ary[0], hoge(ary[1..ary.size-1], &f))
end
puts hoge([1,2,3,4,5]){|x,y| x-y}
もしくは、ブロックを使わずに
def hoge2(ary, f)
return 0 if ary.empty?
return ary[0] if ary.size == 1
return f.call(ary[0], hoge2(ary[1..ary.size-1], f))
end
puts hoge2([1,2,3,4,5], lambda{|x,y| x-y})
(ブロックを関数に渡すのは、Ruby のブロックと Proc を参照)
こうやってみると、Ruby の .call の呼出しは可読性が下がるなぁ (@_@;) それに対して、Haskell の関数を中置演算子のように扱える ` ` の機能はいい。
8. 書き方いろいろ
ところで、【RubyKaigi'08】詳細レポート : 多様化するRuby：CodeZine に
「1から10までの合計を求めるプログラム（多様性の例）」
として、Rubyハッカー、実務プログラマー、研究者の書き方の例が載っていた。各々、「inject 、for、lamda と再帰」を使った方法で書かれていた。
研究者として書かれていたのは、次の通りだった。
lambda{fn=lambda{|x| return 0 if x==0; x+fn.call(x-1)}}.call.call(10)
lambda がネストしているので、理解しづらい。ただし、今回の記事と、Ruby のブロックと Proc を理解しておけば OK 。
0コメント:
コメントを投稿