0. 概要
- 普通、「特定の構造に対して適用する関数」は、特定の型を前提として考える。
- これに対して、構造を辿る関数を与えることによって、「特定の型を前提としない関数」を定義することができる。
前者の方法と比べながら、後者について見ていく。
目次：
- 1. 型を決めてから、関数を定義する
- リストに適用する関数の場合
- 木に適用する関数の場合
- 2. 特定の構造を前提としない関数
- treewalk 関数の引数について
- 第4引数 walker がイメージしにくい理由
- ノードを辿っていく関数 walker
- treewalk 関数のまとめ
- treewalk 関数の使い方
- Data.Tree 型の値に対して treewalk 関数を適用
- リストに対して treewalk 関数を適用
- 3. 要素を辿っていく walk 関数について、はじめから再考
- Data.Tree 型に対して、walk 関数を適用
- リストに対して、walk 関数を適用
- 3-1. walk 関数から、要素に適用する関数を分離
- Data.Tree に対して、walk 関数を適用
- リストに対して、walk 関数を適用
- 3-2. walk 関数から、更に述語を分離
- Data.Tree に対して、walk 関数を適用
- リストに対して、walk 関数を適用
1. 型を決めてから、関数を定義する
リストに適用する関数の場合
リストの要素に、関数を適用するには、map 関数を使う。
例えば、要素を 2 倍したいなら、
*Main> map (* 2) [1..5] [2,4,6,8,10]
map 関数は、「リスト」という構造を前提に定義されている。定義を確認すると、
map :: (a -> b) -> [a] -> [b] map _ [] = [] map f (x:xs) = f x : map f xs
第 2 引数は関数の対象であるリスト。
第 1 引数である関数 f は、データコンストラクタ (:) を使い、リスト構造を辿っていくかのように見える。
木に適用する関数の場合
2 つの子を持つ「木」を、以下のように定義したとする。
data Tree a = Leaf a | Branch (Tree a) (Tree a)
deriving Show
tree = Branch (Leaf 1)
(Branch (Branch (Leaf 2)
(Leaf 3))
(Leaf 4))
木の「葉」が持つ値に、関数を適用する関数を mapTree とすると、
mapTree f (Leaf x) = Leaf (f x) mapTree f (Branch l r) = Branch (mapTree f l) (mapTree f r)
mapTree 関数を、変数 tree に適用してみる。
*Main> mapTree (*2) tree Branch (Leaf 2) (Branch (Branch (Leaf 4) (Leaf 6)) (Leaf 8))
mapTree 関数も、先ほどの map 関数のように、適用する対象である Tree a 型の構造を前提としている。
型コンストラクタ Tree を、Functor クラスのインスタンスにするなら、
instance Functor Tree where
fmap f (Leaf x) = Leaf (f x)
fmap f (Branch l r) = Branch (fmap f l) (fmap f r)
( cf .Haskell の fmap )
変数 tree に fmap を適用すると、
*Main> fmap (*2) tree Branch (Leaf 2) (Branch (Branch (Leaf 4) (Leaf 6)) (Leaf 8))
この方法も、fmap を具体的に定義するとき、Tree a 型の構造を前提としている。
オブジェクト指向で何か考える場合も、問題領域の対象を整理し、クラスと構造を決めながら、メソッドを実装していく。型と構造を考えつつ、操作を割り当てる。構造を離れて、操作だけを考えることは難しい。
2. 特定の構造を前提としない関数
これに対して、「Scheme:オブジェクト指向表現」 の 抽象化の方向 には、オブジェクト指向と比べながら、関数指向のメリットが述べられている。
自分の理解した範囲で、簡単にまとめると、
- オブジェクト指向では、はじめに「型、構造」を想定し、それに相応しい操作を定義していく。これにより、「型、構造」と操作は不可分となり、操作のためのコンテナが必要となる。
- 関数指向では、「型、構造」を事前に想定しない関数を定義することができる。「型、構造」と操作が独立していることにより、必要な操作を、必要に応じて、定義することができる。これを実現するために、クロージャを用いる。
クロージャに関しては、以下を参照。
脱線するが、上記に関連して、「Why OO sucks」のオブジェクト指向に対する批判を、また、思い出した。
Objection 1 - Data structure and functions should not be bound together
Objects bind functions and data structures together in indivisible units. I think this is a fundamental error since functions and data structures belong in totally different worlds. Why is this?
- Functions do things. They have inputs and outputs. The inputs and outputs are data structures, which get changed by the functions. In most languages functions are built from sequences of imperatives: "Do this and then that ..." to understand functions you have to understand the order in which things get done (In lazy FPLs and logical languages this restriction is relaxed).
- Data structures just are. They don't do anything. They are intrinsically declarative. "Understanding" a data structure is a lot easier than "understanding" a function.
（装飾は引用者による）
「Scheme:オブジェクト指向表現」 の 抽象化の方向に戻り、少し長めに引用する。
関数指向の考え方をちょっと示してみます。 与えられた「木」のすべての葉を深さ優先で辿り、与えられた処理を施して行く、という処理を考えてみます。 但し、木の具体的な実装はわかりません。…
関数型では、抽象的な「木」に関する可能な操作を直接関数で渡してやります。
(define (tree-walk tree proc leaf? walker) (define (rec node) (walker (lambda (n) (if (leaf? n) (proc n) (rec n))) node)) (if (leaf? tree) (proc tree) (rec tree)))ここで、leaf? は木のノードを取り、それが葉かそうでないかを返す関数、 walkerは関数と木のノードを取り、ノードのすべての子供に対して渡された関数を適用する関数。…
関数指向のメリットは、tree型に対して適用可能な操作というものを限定していないことです。tree-walkを適用したくなったら、leaf? と walkerに相当する関数を(なんならその場ででも)作って渡してやれば良いのです。…
- (Shiro) この木の例に関しては、コンスセルによる表現を全く仮定していないっす。 (walkerはリストを返す、とかいう制約もついていません)。コンスセルだろうがアレイだろうが適当なコンテナタイプだろうがファイルシステムだろうが、詳細をクロージャの中に隠蔽する、というのがクロージャ指向 :-) の流儀だと思います。
（装飾は引用者による）
先ほど述べたように、関数を適用する対象の構造を前提とせず、構造は後回しにして、関数を定義。クラス指向のように、型と操作が密結合してないので、必要に応じて、構造に対する操作を関数に渡せば良い。
しかし、例としてあげられていた関数を、スラスラと理解できないので、ゆっくりと確認していくことに。 (+_+)
とりあえず、Scheme は見慣れてないので、上記 tree-walk を Haskell で書いてみる。
treewalk tree proc isLeaf walker = if isLeaf tree
then proc tree
else rec tree
where
rec node = walker (\n -> if isLeaf n
then proc n
else rec n)
node
if の部分を整理して、
treewalk tree proc isLeaf walker = treewalk' tree
where
treewalk' = \n -> if isLeaf n
then proc n
else walker treewalk' n
う－ん、これでもまだ、動作のイメージがつかめない。。(@_@;
treewalk 関数の引数について
treewalk 関数の引数を、一つ一つ見ていく。
-
第 1 引数 tree : treewalk を適用する対象
-
第 2 引数 proc : 葉に適用する関数
-
第 3 引数 isLeaf : ノードが葉である場合に、真を返す述語
イメージしにくいのは、第 4 引数 walker 。この関数が使われているのは、上記コードの3 行目。
walker treewalk’ n
tree-walk 関数の説明より、適用対象が「木」であるとき、walker の
-
第 2 引数は、木のノード。（親ノード）
-
第 1 引数は、木のノード（子ノード）に適用する関数。
となるように、利用が想定されている。ただし、あくまでも「想定」であり、使う側が機能を満たすように実装する必要がある。
第4引数 walker がイメージしにくい理由
treewalk 関数の機能は、以下の通りだった。
与えられた「木」のすべての葉を深さ優先で辿り、与えられた処理を施して行く
定義した関数の引数の名前を使い、言い換えると、
対象 tree に対して、要素が isLeaf 関数で真となる「葉」に、関数 proc を適用する
treewalk 関数の実装を見ると、すべての葉を「辿る」ための手段が具体的に書かれていない。いきなりノードに対する処理が記述されおり、walker が何をするか不明なまま、関数が再帰的に定義されているように見える。この点がイメージしにくいところ。
ノードを辿っていく関数 walker
![CropperCapture[310]](http://lh6.ggpht.com/-AW8JXG_65QA/TmYQ5XLO9UI/AAAAAAAAA9k/3C3G3yuYHwE/CropperCapture3105.png?imgmax=800 "CropperCapture[310]")
木のノードを辿るには、親ノードから、その子ノードへ辿る方法が必要となる。どこかに定義されていなくては、木の要素を辿れない。 treewalk 関数において、その具体的な方法が期待されるのが walker 。
walker を加え、もう一度、言い換えると、
対象 tree に対して、要素を辿るために walker を使い、要素が isLeaf 関数で真となる「葉」に、proc を適用する
今回は、すべての葉を対象に proc 関数を適用したい。よって、次のように walker の役割を想定することになる。
-
第4引数 walker : 与えられたノードから辿ることのできる、子ノードに対して、関数を適用する。
このように、walker にノードの辿り方を任せるメリットは、treewalk 関数のような、特定の構造を前提としない関数を定義できることにある。関数の適用対象の構造が変われば、walker を取り替えるだけで済むため、異なる構造に対して、共通部分を抽出できる。
結果的に walker を、
構造を結びつける関数
と見なすことができる。
treewalk 関数のまとめ
treewalk で行っていることをまとめると、
- 対象のノードが葉の場合、ノードに proc を適用する。
- 対象のノードが葉ではない場合、walker に、そのノードと関数を与え、与えたノードから辿ることができる子ノードに関数を適用する。
treewalk 関数の型を調べると、
treewalk :: t1 -> (t1 -> t) -> (t1 -> Bool) -> ((t1 -> t) -> t1 -> t) -> t
第1引数が、特定の型に縛られていないことがわかる。
treewalk 関数の使い方
先ほど使った変数 tree に、treewalk 関数を適用するには、次のように引数を与える。
main = do print $ treewalk tree
(\(Leaf x) -> Leaf (x * 2))
(\n -> case n of
Leaf _ -> True
Branch _ _ -> False)
(\f (Branch l r) -> Branch (f l) (f r))
- 第2引数は、葉に対する処理。
- 第3引数は、葉であるときに真を返す関数。
第 4 引数の walker は、親となるノード（walker の第 2 引数）から、辿ることができる子ノードに対して、関数（walker 関数の第1引数）を適用する。結果は、以下のようになる。
Branch (Leaf 2) (Branch (Branch (Leaf 4) (Leaf 6)) (Leaf 8))
Data.Tree 型の値に対して treewalk 関数を適用
同じ treewalk 関数を使い、Data.Tree 型の値に適用してみる。
import Data.Tree
tree2 = Node 1 [ Node 2 []
, Node 3 [ Node 4 []
, Node 5 []
, Node 6 []]]
これに対して、
main = print $ treewalk tree2
(\(Node x xs) -> Node (x*2) xs)
(\n -> case n of
Node x [] -> True
otherwise -> False)
(\f (Node x xs) -> Node x (map f xs))
子を持たない Node を「葉」と見なし、ノードを辿る walker は、先ほどの定義を少し変更するだけで済んだ。
![CropperCapture[311]](http://lh6.ggpht.com/-HDbJHbg80_w/TmYQ5zcUn3I/AAAAAAAAA9o/K6VsJv9ilcI/CropperCapture3115.png?imgmax=800 "CropperCapture[311]")
結果は、
Node { rootLabel = 1
, subForest = [ Node { rootLabel = 4
, subForest = []
}
, Node { rootLabel = 3
, subForest = [ Node { rootLabel = 8
, subForest = []
}
, Node { rootLabel = 10
, subForest = []
}
, Node { rootLabel = 12
, subForest = []
}
]
}
]
}
ちなみに、「葉」に対してのみ、関数が適用されるので、子を持つノードの値は変わらない。
リストに対して treewalk 関数を適用
では、treewalk 関数を使って、リストの要素を 2 倍できるだろうか？
リストの場合、各要素をすべて「葉」と見なし、walker が次の要素へと辿るように考えればいいのかな…
![CropperCapture[312]](http://lh5.ggpht.com/-EK5jLyaKV0Q/TmYQ6KB-OAI/AAAAAAAAA9s/_kluX0lsi4g/CropperCapture3125.png?imgmax=800 "CropperCapture[312]")
print $ treewalk [0..5]
(\(x:xs) -> (x*2) : xs)
(\_ -> True)
(\f n -> case n of
x : xs -> x : f xs
[] -> [])
しかし、結果、要素は 2 倍されなかった。。 (+_+)
理由は、treewalk が proc を適用するのは「葉」に対してだけれど、walker がノードを辿るのは、葉ではない要素であるため。リストの各要素を、「葉である」と同時に「子ノードを持つ」と見なしたので、proc を適用できなかった。先ほど Data.Tree 型の値に対して、treewalk 関数を適用したら、子を持つノードの値が変わらなかったことと同じ。
3. 要素を辿っていく walk 関数について、はじめから再考
treewalk 関数のように、要素を辿る関数について、単純な形から考えてみる。
まずは、以下の 2 つの引数を与える関数。
-
第 2 引数: ノード (node)
-
第 1 引数: 上記ノードから辿ることができる要素に、関数を適用していく、と想定する関数 (walker)
関数名を walk とすると、定義は以下の通り。
walk walker node = walker (\n -> walk walker n)
node
改めて、適用対象の「木」の型を、以下のように定義する。
data BinaryTree a = Leaf a
| Branch (BinaryTree a) a (BinaryTree a)
deriving Show
適当に値を作る。
tree = Branch (Leaf 1)
100
(Branch (Leaf 2)
200
(Leaf 3))
これに対し、walk 関数を適用してみる。要素を辿るだけで、何もせず、そのまま返すには、
print $ walk (\f n -> case n of
Leaf x -> Leaf x
Branch l x r -> Branch (f l) x (f r))
tree
=> Branch (Leaf 1) 100 (Branch (Leaf 2) 200 (Leaf 3))
葉を 2 倍し、枝を 3 倍するなら、
print $ walk (\f n -> case n of
Leaf x -> Leaf (x*2)
Branch l x r -> Branch (f l) (x*3) (f r))
tree
=> Branch (Leaf 2) 300 (Branch (Leaf 4) 600 (Leaf 6))
Data.Tree 型に対して、walk 関数を適用
次に、先ほど使った Data.Tree 型の値 (tree2) に、同じように walk 関数を適用してみる。
-- 何もしないで、そのまま返す
print $ walk (\f n -> case n of
Node x [] -> Node x []
Node x xs -> Node x $ map f xs)
tree2
-- 葉を 2 倍し、枝を 3 倍する
print $ walk (\f n -> case n of
Node x [] -> Node (x*2) []
Node x xs -> Node (x*3) $ map f xs)
tree2
リストに対して、walk 関数を適用
リストに対して、walk 関数を適用してみる。
print $ walk (\f n -> case n of
[] -> []
x : xs -> x : f xs)
[0..5]
print $ walk (\f n -> case n of
[] -> []
x : xs -> (x*2) : f xs)
[0..5]
3-1. walk 関数から、要素に適用する関数を分離
上記の方法は、
- ノードを辿っていくこと
- ノードに関数を適用すること
の 2 つを同時に行っている。これを分離したい。
「ある構造を持つ型に対して、各要素を辿り、特定の関数を適用する関数」に変更。
walk f walker node = walker (\n -> walk f walker n)
(f node)
- 第1引数 f は、要素に適用する関数。
その他は同じ。
これを使い、何もしないで、そのまま返すには、
print $ walk id
(\f n -> case n of
Leaf x -> Leaf x
Branch l x r -> Branch (f l) x (f r))
tree
=> Branch (Leaf 1) 100 (Branch (Leaf 2) 200 (Leaf 3))
要素を辿る関数を使いまわしたいので、別に定義しておく。
walkBinaryTree _ (Leaf x) = Leaf x walkBinaryTree f (Branch l x r) = Branch (f l) x (f r)
葉は 2 倍し、枝を 3 倍するなら、
print $ walk (\n -> case n of
Leaf x -> Leaf (x*2)
Branch l x r -> Branch l (x*3) r)
walkBinaryTree
tree
=> Branch (Leaf 2) 300 (Branch (Leaf 4) 600 (Leaf 6))
要素に適用する関数も使いまわしたいので、別に定義。
doubleLeafTripleBranch (Leaf x) = Leaf $ x*2 doubleLeafTripleBranch (Branch l x r) = Branch l (x*3) r
要素を辿ったとき、リストを返して欲しいなら、
walkBinaryTree2List _ (Leaf x) = [x] walkBinaryTree2List f (Branch l x r) = x : f l ++ f r
これを使い、
print $ walk doubleLeafTripleBranch
walkBinaryTree2List
tree
=> [300,2,600,4,6]
逆に辿りたい場合は、辿り方を変更する。
reverseWalkBinaryTree2List _ (Leaf x) = [x] reverseWalkBinaryTree2List f (Branch l x r) = f r ++ f l ++ [x]
これを使い、
print $ walk doubleLeafTripleBranch
reverseWalkBinaryTree2List
tree
=> [6,4,600,2,300]
Data.Tree に対して、walk 関数を適用
次に、Data.Tree 型の値を対象にする。
Node の辿り方と、要素に適用する関数を予め定義。
walkTree f (Node x xs) = Node x (map f xs) doubleNodeTripleBranch (Node x []) = Node (x*2) [] doubleNodeTripleBranch (Node x xs) = Node (x*3) xs
これを使い、
print $ walk doubleNodeTripleBranch
walkTree
tree2
=> Node { rootLabel = 3
, subForest = [ Node { rootLabel = 4
, subForest = []
}
, Node { rootLabel = 9
, subForest = [ Node { rootLabel = 8
, subForest = []
}
, Node { rootLabel = 10
, subForest = []
}
, Node { rootLabel = 12
, subForest = []
}
]
}
]
}
リストに対して、walk 関数を適用
同じく、リストの場合。
要素の辿り方と、要素に適用する関数を予め定義しておく。
walkList _ [] = [] walkList f (x:xs) = x : f xs doubleElem [] = [] doubleElem (x:xs) = (x*2) : xs
これを使い、
print $ walk doubleElem
walkList
xs
=> [2,4,6,8,10]
3-2. walk 関数から、更に述語を分離
次に、変数 tree に戻り、「偶数であるノードの値」に対して、葉を 2 倍し、枝を 3 倍したいとする。
print $ walk (\n -> case n of
Leaf x | even x -> Leaf (x*2)
Branch l x r | even x -> Branch l (x*3) r
node -> node)
walkBinaryTree
tree
=> Branch (Leaf 1) 300 (Branch (Leaf 4) 600 (Leaf 3))
- 要素に対して関数を適用する
- 要素が条件を満たしているか検査する
という 2 つのことを同時に行っているので、これを分離してみる。
walk p f walker node = walker (\n -> walk p f walker n)
(if p node then f node else node)
第1引数 p は述語で、これが真である場合、第2引数 f をノードに適用する。
予め、ノードの値が、偶数である場合、真を返す述語を定義。
isNodeEven (Leaf x) | even x = True isNodeEven (Branch l x r) | even x = True isNodeEven _ = False
これを使い、
print $ walk isNodeEven
doubleLeafTripleBranch
walkBinaryTree
tree
=> Branch (Leaf 1) 300 (Branch (Leaf 4) 600 (Leaf 3))
結果をリストにするなら、
print $ walk isNodeEven
doubleLeafTripleBranch
walkBinaryTree2List
tree
[300,1,600,4,3]
Data.Tree に対して、walk 関数を適用
Data.Tree 型の値を対象にする場合、
print $ walk (\n -> case n of
Node x xs | even x -> True
otherwise -> False)
doubleNodeTripleBranch
walkTree
tree2
=> Node { rootLabel = 1
, subForest = [ Node { rootLabel = 4
, subForest = []
}
, Node { rootLabel = 3
, subForest = [ Node { rootLabel = 8
, subForest = []
}
, Node { rootLabel = 5
, subForest = []
}
, Node { rootLabel = 12
, subForest = []
}
]
}
]
}
リストに対して、walk 関数を適用
リストを対象にする場合、
print $ walk (\n -> case n of
x : _ | even x -> True
otherwise -> False)
doubleElem
walkList
xs
[1,4,3,8,5]
このように、構造を辿る方法を抽象化しておくと、同じ関数を使い回し、組み合わせることができるようだ。
