Rubyを使って「なぜ関数プログラミングは重要か」を解読しよう！(その２)
前回に引き続き「なぜ関数プログラミングは重要か」を、Rubyを使って解釈し自分の理解に基づいて解説してみます。
関数の貼り合せ（ツリー編）
貼り合せの能力はリスト上の関数にとどまらない。ラベル付き順序ツリーの例でこれを示そう。
Rubyにはリストに都合の良いArrayクラスが組込みであったが、ツリーに都合の良いものはないので自分でクラスを定義しよう。ツリーはラベルを持ったノードを連結したものとして表現できるので、この連結の機能をもったNodeクラスを定義することでツリーを表現しよう。
class Node
attr_reader :label, :subtrees
def initialize(label, *subtrees)
@label = label
@subtrees = subtrees
end
end
def node
->label,*subtrees{ Node.new(label, *subtrees) }
endノードオブジェクトはlabelとサブノードのリストsubtreesをもつことができる。ここではノードオブジェクトを関数言語風に生成するために、node関数(Objectクラスのメソッド)を用意している。
例えば、
1 o
／ ＼
／ ＼
／ ＼
2 o o 3
|
|
|
o 4というツリーはこのNodeクラスを使って以下のように表現できる。
tree = node[1,
node[2],
node[3, node[4]]
]
# >> #<Node:0x0a431c @label=1, @subtrees=[#<Node:0x0a4420 @label=2, @subtrees=[]>, #<Node:0x0a4358 @label=3, @subtrees=[#<Node:0x0a4394 @label=4, @subtrees=[]>]>]>つまりノード１は２つのノード２，３をサブノードとしてもち、ノード３はノード４をサブノードとしてもっている。nodeの第２引数は省略できこの場合subtreesの値は[ ]になる。
さてここで、リストで用意したreduceメソッドと同じ目的をツリーで果たすred_treeメソッドを定義してみよう。
リストのところの説明でreduceがリストを生成するconsとの比較で、consと[ ]をfとaに置き換えたものとみなせると言った。同じ発想でツリーがリストを含むノードで生成される、つまりnodeとconsと[ ]で生成できることから、red_treeはこれらをfとgとaに置き換えたものとみなせる。
ここでツリーとリストは別のクラスなので、それぞれのクラスの上にred_treeを定義する必要がある。
class Node
def red_tree(f, g, a)
f[label, subtrees.red_tree(f, g, a)]
end
end
class Array
def red_tree(f, g, a)
return a if empty?
g[head.red_tree(f, g, a), tail.red_tree(f, g, a)]
end
endここで最初の引数である関数fはノードオブジェクトの要素に適用され、第２の引数である関数gはリストの要素に適用される。red_treeと他の関数を貼り合せることで興味深い関数がいくつも定義できる。
次の段階に進む前にArrayクラスに定義した有用なメソッド群をNodeクラスにも定義したい。ここではNodeクラスに同じものを用意するのではなく、Arrayクラスのそれらのメソッドをモジュールに抽出してNodeクラスでも使えるようにしよう。
module Functional
def cons
->(x,ls=self){ [x] + ls }
end
def append
->(ls,se=self){ ls.reduce cons, se }
end
def add
->x,y{ x + y }
end
def double
->num{ 2 * num }
end
def compose(f,g)
->x,y{ f[g[x],y] }
end
end
class Array
include Functional
end
class Node
include Functional
end準備ができたので、まずツリーのラベルの数値をすべて足すsum_treeを定義しよう。
class Node
def sum_tree
red_tree add, add, 0
end
end
tree = node[1,
node[2],
node[3, node[4]]
]
tree.sum_tree # => 10ツリーのlabel全体のリストは以下のように定義できる。
class Node
def labels
red_tree cons, append, []
end
end
tree.labels # => [1, 2, 3, 4]最後にリストのmapと類似したメソッドつまり関数fをツリーのすべてのラベルに適用するメソッドmap_treeを定義する。
class Node
def map_tree(f)
red_tree compose(node, f), cons, []
end
endmap_treeを使えば、たとえばラベルの数値を倍にするメソッドを定義できる。
class Node
def double_all
map_tree double
end
end
tree.double_all.labels # => [2, 4, 6, 8]以上のように高階関数すなわち関数を引数に取ったり、関数を返したりすることができる関数を使うことにより、プログラムを柔軟に多数の汎用的な部品に分割できるようになる。
(続く？)
(追記：2011-2-1)続きを書きました。
Rubyを使って「なぜ関数プログラミングは重要か」を解読しよう！(その３)
blog comments powered by Disqus
