前回に引き続き「なぜ関数プログラミングは重要か」を、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=[]>]>]>

つまりノード1は2つのノード2,3をサブノードとしてもち、ノード3はノード4をサブノードとしてもっている。nodeの第2引数は省略できこの場合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はノードオブジェクトの要素に適用され、第2の引数である関数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
end

map_treeを使えば、たとえばラベルの数値を倍にするメソッドを定義できる。

class Node
  def double_all
    map_tree double
  end
end
tree.double_all.labels # => [2, 4, 6, 8]

以上のように高階関数すなわち関数を引数に取ったり、関数を返したりすることができる関数を使うことにより、プログラムを柔軟に多数の汎用的な部品に分割できるようになる。

(続く?)

(追記:2011-2-1)続きを書きました。

Rubyを使って「なぜ関数プログラミングは重要か」を解読しよう!(その3)



blog comments powered by Disqus
ruby_pack8

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