先日、関数型の初心者の勉強会に参加してきました。
私は、もともと情報系の学科を卒業したわけではないので、アルゴリズムや関数型の考え方は全くの初心者です。
なので、再帰の考え方に慣れるのにとても大変でした。まだ慣れているとは言えないレベルですが。。
備忘録もかねて、rubyで実装してみたいと思います。
今回はmapを実装してみたいと思います。rubyのmap関数はよく使うと思いますが、
配列の各要素に対してある処理を施し同じく配列を返す関数です。
こんな感じですね。
["1", "2", "3"].map { |num| num.to_i } ["1", "2", "3"].map(&:to_i)
各要素をFixnum型にしています。
今回のmapは引数は二つ。
一つ目は処理の対象となる配列。二つ目は処理を施したい関数です。
rubyの場合、関数をオブジェクトにするのはprocとかlambdaですので、これを利用します。
※proc、lambdaについてはこのあたりの記事がわかりやすいです。
http://qiita.com/kidach1/items/15cfee9ec66804c3afd2
Rubyの ブロック、Proc.new、lambdaの違い - Qiita
ではさっそく、こんな感じで実装してみました。
def map(array, f) return [] if array.empty? [f.call(array[0])] + map(array[1..-1], f) end # もちろんarray.firstやarray.drop(0)を利用してもOK。
1個目の要素に処理をして残りの配列をもう一度自分自身に引き渡す。
実際に手で処理を追っていくと理解が深まりそうです。
だんだんやっていくと空配列になるので、そのときは処理は終わるようにしています。
実際に使ってみた例はこんな感じです。
[1] pry(main)> def map(array, f) [1] pry(main)* return [] if array.empty? [1] pry(main)* [f.call(array[0])] + map(array[1..-1], f) [1] pry(main)* end => :map [2] pry(main)> twice = ->(x) { x * 2 } => #<Proc:0x007fc3c2c82700@(pry):5 (lambda)> [3] pry(main)> map([1,2,3,4,5], twice) => [2, 4, 6, 8, 10]
ただし、このような再帰関数でうと、関数呼び出しの階数が深くなるとスタックオーバーフローが発生してしまいます。
そこで使うのが末尾再帰というものだそうです。
実装してみた結果がこんな感じです。
def map(array, f, result = []) return result if array.empty? map(array[1..-1], f, result + [f.call(array[0])]) end
今度はどんどんresultに新しい配列が入っていくので空配列になったときはresultを返すようにします。
配列の掛け算や足し算をする処理なんかも再帰を使って書くとすっきりします。
def sum(array) return 0 if array.empty? array[0] + sum(array[1..-1]) end def product(array) return 1 if array.empty? array[0] * product(array[1..-1]) end
左畳み込みと右畳み込みがあり、今回は、配列の左側から処理をしていっているので、左畳み込みで処理をしてみました。
