0. 目次：
- 1. 型を処理する高階関数を考える視点
- 2. リストのデータコンストラクタを置き換える関数
- a. reduceList 関数の定義
- b. reduceList で要素を足し上げる
- c. reduceList で同じ値を返す
- d. reduceList から map 関数を導く
- e. reduceList から filter 関数
- f. 述語を満たす要素に、特定の関数を適用する
- g. reduceList からリストを結合する関数
- h. reduceList でリストを逆順にする関数
- i. Haskell の標準ライブラリにある foldr
- 3-1. 二分木でデータコンストラクタを置き換える関数 (1) – 左右の子が必ずある場合
- a. reduceBinaryTree 関数の定義
- b. reduceBinaryTree 関数から、map, filter 関数を導く
- 3-2. 二分木でデータコンストラクタを置き換える関数 (2) – 左右の子が必ずしも存在しない場合
- a. reduceBinaryTree 関数の定義
- b. reduceBinaryTree 関数から、map, filter 関数を導く
- 4-1. 0 個以上の子を持つ木で、データコンストラクタを置き換える関数
- a. reduceTree 関数を定義
- b. 定義済の List a 型の reduceList 関数を利用する場合
- c. reduceTree 関数から map 関数を導く
- 4-2. 木のリストで、データコンストラクタを置き換える関数
- a. 木のリストのデータコンストラクタを置き換える関数
- 5. 余談： 他の関数を導くための reduce 関数と、畳み込み関数を混同していた
- a. reduce 関数は、畳み込み関数とは違う
- b. 「畳み込み関数」とは
- c. リストの foldr の定義により混同した
- d. その型を処理する高階関数を何と呼ぶべきか？
- e. fold, reduce の言葉の意味について
- f. reduce 関数を理解するために重要な点
- g. reduce 関数とは何か？
1. 型を処理する高階関数を考える視点
「なぜ関数プログラミングは重要か」には、高階関数の利点について、次のように述べられている。
… 高階関数は、一度定義すると、非常に簡単に数多くの演算をプログラムすることができる。新しいデータ型を定義したときにその型を処理する高階関数を書くべきである。そうすれば、そのデータ型の取り扱いが簡単になり、その表現の詳細に関する知識を局所化できる。
（「3. 関数の貼り合せ」より、装飾は引用者による、以下、「なぜ関数...」と略す）
上記で述べられている、高階関数を定義するポイントは、
- 対象となる型の「データコンストラクタを置き換える関数」を与える関数
を考えること。
2. リストのデータコンストラクタを置き換える関数
Haskell では、リストを書くのに、特別な記法が用意されている。
The Haskell 98 Report: 定義ずみの型とクラス によると、
data [a] = [] | a : [a] deriving (Eq, Ord)
リストは、二つの構築子をもつ代数的データ型であるが、3.7 節で述べたように特別な構文をもつ。最初 の構築子は空リストで、`[]' (「ニル」)と書く。二つ目の構築子 は、`:' (「コンス」)と書く。
ただし、「データコンストラクタを置き換えること」を考える場合、Haskell で用意されているリストの記法を使うよりも、自分でリスト型を定義して考える方が理解しやすい。
理由は、リストに適用する関数を定義するとき、パターンマッチで、(:) を二項演算子のようにして書くことが多いため。例えば、リストの長さを知るための関数 length を、以下のように定義したとする。
length [] = 0
length (x:xs) = 1 + length xs
2行目のパターンマッチを、二項演算子のような扱いをせず、以下のように書くこともできる。
length ((:) x xs) = 1 + length xs
このように書いた方が、「データコンストラクタを置き換える」ことを考えるとき、置き換える対象の対応をつけやすい。しかし、あまり、後者のような書き方をしているのを見たことがない。
そのため、ここではリスト型を、以下のように定義したものを使う。Haskell のリストと同じように、リストの末尾が空リスト。リストに追加する要素を、リストの先頭に追加することを意図した代数的データ型の定義。
data List a = Nil
| Cons a (List a)
deriving Show
List a 型のデータコンストラクタは 2 つ。これを次のようなものだと考える。
- Cons は 2 つの引数を取る関数。
- Nil は引数がない関数、もしくは、定数。
実際、データコンストラクタの型を調べて見ると、
*Main> :t Cons
Cons :: a -> List a -> List a
*Main> :t Nil
Nil :: List a
この List a 型のデータコンストラクタを使い、適当に値を作る。
xs = Cons 1 (Cons 2 (Cons 3 Nil))
ここで、上記の変数 xs の値を見ながら、「データコンストラクタを置き換えるを関数」をイメージする。
データコンストラクタと置き換える関数とは、具体的には、
- Cons に対応した、2 つの引数を取る任意の関数 f
- Nil に対応した、任意の値である z
データコンストラクタを、任意の関数 f, z で置き換えた状態を、変数 xs で考えると、以下のようになる。
f 1 (f 2 (f 3 z))
上記の計算において、関数 f, z に具体的な関数を与え、変数を評価すれば、値を得ることができる。f, z は任意の関数なので、目的に応じて、行いたい計算を与えれば、データコンストラクタが持っていた値を用いて、計算できる。
データコンストラクタは、パターンマッチに利用できる特殊な関数であることを除けば、
f 1 (f 2 (f 3 z))
という計算から導かれた、特殊な一形態に過ぎないと見ることができる。
a. reduceList 関数の定義
では、リストのデータコンストラクタを、任意の関数に置き換える reduceList を定義する。
データコンストラクタ Nil に対する定義は簡単。 Nil を z で置き換えればいいので、
reduceList f z Nil = z
データコンストラクタ Cons は、再帰的な視点が必要になる。まずは、細かいことを考えずに、Cons の部分を f に置き換えてみる。
reduceList f z (Cons x xs) = f x xs
この定義では、パターンマッチで Cons が分解した、List a 型の値である xs に対して、何も行なっていない。
試しに、この定義のまま、reduceList 関数の型を確認すると、
*List> :t reduceList
reduceList :: (t1 -> List t1 -> t) -> t -> List t1 -> t
reduceList 関数の第1引数には、二項演算子を与える。ただし、今のままでは、その第1引数は、List t1 型に固定されている。この型を、reduceList 関数の第1引数が返す値と同じ、任意の型 t になるような定義にしたい。そのためには、データコンストラクタ Cons の、再帰的な定義に注目する。
reduceList 関数の第１引数 f は、データコンストラクタ Cons を置き換えることを目的としていた。reduceList 関数の適用対象である、第３引数の Cons x xs のの xs はリスト型。この変数 xs の個々の要素に対して、 Cons を、関数 f で置き換えたい。そのためには、再帰的に、reduceList 関数を適用していけばよい。
よって、以下の定義となる。
reduceList f z (Cons x xs) = f x (reduceList f z xs)
これにより、reduceList の第1引数の関数の型が、リスト型から解放される。
もう一度、reduceList 関数の型を確認してみると、
*List> :t reduceList
reduceList :: (t1 -> t -> t) -> t -> List t1 -> t
繰り返しになるが、 reduceList の引数 z は Nil と置き換えることを意図し、f は Cons と置き換えることを意図していた。この 2 つ引数が必要なのは、リストのデータコンストラクタは２種類存在し、reduceList 関数は、その２つを置き換えることを目的としていたから。
( cf.jutememo's gist: 1322202 — Gist )
b. reduceList で要素を足し上げる
最初に、reduceList 関数を使い、リストの要素を足し上げてみる。
*List> reduceList (+) 0 xs
6
これは、リストのデータコンストラクタ Cons を (+) で置き換え、Nil を 0 で置き換えて、計算を行なっている、とイメージすることができる。
(+) 1 ((+) 2 ((+) 3 0))
この例から、reduceList 関数は、リストのデータコンストラクタに位置するものを、他の関数や値に置き換えていることを実感できる。
c. reduceList で同じ値を返す
次に、与えられたリストを、変化させずに返す関数を定義してみる。
idList = reduceList Cons Nil
これは、以下のように元の値が生成される。
Cons 1 (Cons 2 (Cons 3 Nil))
一度、与えられた値を分解し、それをまた同じ種類の関数で、貼り付け直すイメージ。
d. reduceList から map 関数を導く
リストの各要素に、関数を適用する関数を mapList とする。
これまでと同様に、データコンストラクタを置き換えるイメージで行えばよい。
考えるための元の計算の形は、
f 1 (f 2 (f 3 z))
まずは、関数 f に相当するものは何か？その適用対象は何か？を考える。
-
関数 f の第１引数は、データコンストラクタ Cons が持っている値。（ Cons x xs の x の方）
-
第 2 引数は、後方のリスト。( Cons x xs の xs の方)
mapList 関数は、リストの要素に対して、関数を適用したいので、Cons x xs の x に対して関数を適用する。 xs の方はそのままで、何もしない。よって、関数 f は以下のように定義できる。
\x xs -> Cons (f x) xs
上記の無名関数を、f と置き換え、適用するところを、一部イメージすると、
(\x xs -> Cons (f x) xs) 1 (...)
最後まで書くと、
(\x xs -> Cons (f x) xs) 1 ((\x xs -> Cons (f x) xs) 2 ((\x xs -> Cons (f x) xs) 3 Nil))
よって、mapList 関数の定義は、以下のようになる。
mapList f = reduceList (\x xs -> Cons (f x) xs) Nil
関数を合成するための関数 (.) を使うなら、
mapList f = reduceList (Cons . f) Nil
( cf.jutememo's gist: 1322202 — Gist )
e. reduceList から filter 関数
次に、リストの要素から、述語 p を満たす要素のみを抽出する filterList 関数を定義したい。
この場合も、mapList を定義したときと同じように、
「データコンストラクタを置き換えた場合、どう定義すればいいのか？」
を考えれば良い。
filterList p = reduceList (\x xs ->
if p x then Cons x xs
else xs)
Nil
実際に使ってみる。
*List> filterList even xs
Cons 2 Nil
*List> filterList odd xs
Cons 1 (Cons 3 Nil)
f. 述語を満たす要素に、特定の関数を適用する
mapList と filterList を定義できたので、2つの関数を合成して、「述語を満たす要素を抽出して、特定の関数を適用する関数」を定義してみる。
mapListIf p f = mapList f . filterList p
この関数を使うと、
*List> mapListIf even (* 10) xs
Cons 20 Nil
*List> mapListIf odd (* 10) xs
Cons 10 (Cons 30 Nil)
ただし、この定義だと、述語を満たさない要素は、取り除かれてしまう。
述語を満たさない要素も、そのままリストに残したい場合は、reduceList 関数から、導くことができる。
mapListIf p f = reduceList (\x xs ->
if p x then Cons (f x) xs
else Cons x xs)
Nil
試してみる。
*List> mapListIf even (* 10) xs
Cons 1 (Cons 20 (Cons 3 Nil))
*List> mapListIf odd (* 10) xs
Cons 10 (Cons 2 (Cons 30 Nil))
( cf.jutememo's gist: 1322202 — Gist )
g. reduceList からリストを結合する関数
リスト同士を結合したいときは、どうすれば良いだろう？
これまでと同じように、以下の式に戻り、z に結合したいリストを当てはめればいいことがわかる。
f 1 (f 2 (f 3 z))
よって、関数名を appendList とすると、関数 f には Cons を与え、z には結合したいリストを与える。
appendList xs1 xs2 = reduceList Cons xs2 xs1
h. reduceList でリストを逆順にする関数
リストを逆順にするには、以下の計算の形から考えて、関数 f の第1引数を、第2引数の後ろに結合することによって定義できることがわかる。
f 1 (f 2 (f 3 z))
よって、上記で定義した appendList 関数を用いて、
reverseList = reduceList (\x xs -> xs `appendList` (Cons x Nil)) Nil
( cf.jutememo's gist: 1322202 — Gist )
i. Haskell の標準ライブラリにある foldr
ここまで来ると、Haskell の標準ライブラリにある foldr も、リストのデータコンストラクタを、置き換える関数を定義することを考えるだけで良いことがわかる。
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
3-1. 二分木でデータコンストラクタを置き換える関数 (1) – 左右の子が必ずある場合
次に、二分木で、データコンストラクタを置き換える関数を考える。
先ほどのリスト型と同じように、型の定義をし、適当に値を作成する。ただし、この二分木は、左右の子を必ず持つとする。（全二分木）
data BinaryTree a = Leaf a
| Branch (BinaryTree a) a (BinaryTree a)
deriving Show
btree = Branch (Leaf 1)
2
(Branch (Leaf 4)
3
(Leaf 5))
ここで、上記の変数 btree の値を見ながら、「データコンストラクタを置き換えるを関数」をイメージする。
データコンストラクタと置き換える関数とは、具体的には、
- Branch に対応した、3 つの引数を取る任意の関数 f
- Leaf に対応した、 1 つの引数を取る任意の関数 g
データコンストラクタを、任意の関数 f, g で置き換えた状態を、変数 btree で考えると、以下のようになる。
f (g 1)
2
(f (g 4)
3
(g 5))
リストで考えたときと同じように、関数 f, g に具体的な関数を与えれば、値を得ることができる。f, g は任意の関数なので、目的に応じて、データコンストラクタが持っている値を用いて計算できる。
データコンストラクタによって、生成された値は、
f (g 1)
2
(f (g 4)
3
(g 5))
の形から導かれた、特殊な一形態と見ることができる。
a. reduceBinaryTree 関数の定義
では、二分木のデータコンストラクタを、任意の関数に置き換える reduceBinaryTree を定義してみる。
データコンストラクタが Leaf のときは簡単。Leaf を g と置き換えるだけ。
reduceBinaryTree f g (Leaf x) = g x
データコンストラクタ Branch を考えるときは、再帰的な視点が必要。まずは、 Branch を f に置き換えるだけの定義。
reduceBinaryTree f g (Branch l x r) = f l x r
この場合、関数の型は、
*BinaryTree> :t reduceBinaryTree
reduceBinaryTree
:: (BinaryTree t -> t -> BinaryTree t -> t1)
-> (t -> t1)
-> BinaryTree t
-> t1
reduceBinaryTree 関数の第1引数に注目すると、その第1, 3引数が、BinaryTree t 型に固定されていることがわかる。この制約をなくすには、BinaryTree a 型の再帰的な構造基づいて、左と右の木に対して、reduceBinaryTree 関数を適用する必要がある。
reduceBinaryTree f g (Branch l x r) = f (reduceBinaryTree f g l)
x
(reduceBinaryTree f g r)
型を確認すると、
*BinaryTree> :t reduceBinaryTree
reduceBinaryTree
:: (t1 -> t -> t1 -> t1) -> (t -> t1) -> BinaryTree t -> t1
これで、データコンストラクタ Branch を関数 f で、Leaf を g で置き換える関数を定義できた。リストのときと同じように、データコンストラクタの形に注目して、置き換えただけ。
( cf.jutememo's gist: 1322202 — Gist )
b. reduceBinaryTree 関数から、map, filter 関数を導く
最初に、reduceBinaryTree 関数を使い、二分木の要素から計算を行なってみる。方法は、
- 木の子ども同士は、掛け合わせ、
- 親子の間は、足し上げる
とする。
*BinaryTree> reduceBinaryTree (\l x r -> x + l * r) id btree
25
次に、元の BinaryTree a 型の値を変化させず、元の値と同じ値を返す関数を定義する。reduceBinaryTree 関数に、データコンストラクタを渡すだけなので、簡単。
idBinaryTree = reduceBinaryTree Branch Leaf
木の要素に、関数を適用する関数を、mapBinaryTree 関数とすると、
mapBinaryTree f = reduceBinaryTree (\l x r -> Branch l (f x) r) (Leaf . f)
使ってみる。
*BinaryTree> mapBinaryTree (*2) btree
Branch (Leaf 2) 4 (Branch (Leaf 8) 6 (Leaf 10))
特定の条件を満たすノードをリストとして返す関数を、filterBinaryTree2List とすると、
filterBinaryTree2List p = reduceBinaryTree (\l x r ->
let lr = l `appendList` r
in if p x then Cons x lr
else lr)
(\x -> if p x then Cons x Nil
else Nil)
使ってみる
*BinaryTree> filterBinaryTree2List odd btree
Cons 1 (Cons 3 (Cons 5 Nil))
( cf.jutememo's gist: 1322202 — Gist )
3-2. 二分木でデータコンストラクタを置き換える関数 (2) – 左右の子が必ずしも存在しない場合
上記の二分木は、左右の子どもを必ず持つ二分木だった。これを、左右の子を必ずしも持たない構造に変更する。
まずは、型の定義から。子がない場合は、データコンストラクタ Empty で表現することにする。
data BinaryTree a = Empty
| Leaf a
| Branch (BinaryTree a) a (BinaryTree a)
deriving Show
適当に値を作る。
btree = Branch (Leaf 1)
2
(Branch (Branch Empty
4
(Leaf 5))
3
Empty)
a. reduceBinaryTree 関数の定義
今回は、先ほどの二分木と比べ、データコンストラクタが一つ増えた。よって、データコンストラクタを置き換える、reduceBinaryTree 関数を定義するとき、引数を一つ増やす必要がある。
reduceBinaryTree f g z Empty = z
reduceBinaryTree f g z (Leaf x) = g x
reduceBinaryTree f g z (Branch l x r) = f (reduceBinaryTree f g z l)
x
(reduceBinaryTree f g z r)
reduceBinaryTree 関数を使い、二分木の要素の値を利用して、計算を行なってみる。方法は、
- 木の子ども同士は、掛け合わせ、
- 親子の間は、足し上げる
とする。ただし、Empty に相当する子はの値を 1 として、計算を行う。
*Main> reduceBinaryTree (\l x r -> x + l * r) id 1 btree
14
( cf.jutememo's gist: 1322202 — Gist )
b. reduceBinaryTree 関数から、map, filter 関数を導く
各要素に関数を適用する mapBinaryTree 関数を定義する。
mapBinaryTree f = reduceBinaryTree (\l x r -> Branch l (f x) r)
(Leaf . f)
Empty
使ってみる。
*Main> mapBinaryTree (*2) btree
Branch (Leaf 2) 4 (Branch (Branch Empty 8 (Leaf 10)) 6 Empty)
特定の条件を満たすノードをリストとして返す関数を、filterBinaryTree2List とすると、
filterBinaryTree2List p = reduceBinaryTree (\l x r ->
let lr = l `appendList` r
in if p x then Cons x lr
else lr)
(\x -> if p x then Cons x Nil
else Nil)
Nil
使ってみる。
*BinaryTree> filterBinaryTree2List even btree
Cons 2 (Cons 4 Nil)
これで、データコンストラクタを置き換える関数を定義したい場合、データコンストラクタの数に合わせて、引数を増やさなければならないことが確認できた。
( cf.jutememo's gist: 1322202 — Gist )
4-1. 0 個以上の子を持つ木で、データコンストラクタを置き換える関数
次に、0 個以上の子を持つ木で、データコンストラクタを置き換える関数を定義してみる。
型の定義は、木が、木のリストを子として持つと想定する。
data Tree a = Node a (List (Tree a)) deriving Show
適当に Tree a 型の値を作る。
tree = Node 1
(Cons (Node 2 Nil)
(Cons (Node 3
(Cons (Node 5 Nil)
(Cons (Node 6 Nil) Nil)))
(Cons (Node 4 Nil) Nil)))
変数 tree で使われているデータコンストラクタは 3 つある。よって、データコンストラクタを置き換える関数を 3 つ考える必要がある。
変数 tree を、関数 f, g, z で置き換えたところを考えると、以下のようになる。
f 1
(g (f 2 z)
(g (f 3
(g (f 5 z)
(g (f 6 z) z)))
(g (f 4 z) z)))
a. reduceTree 関数を定義
reduceTree 関数を定義するために、順にデータコンストラクタを置き換えてみる。
まずは、Node を f へ 置き換え。
reduceTree f g z (Node x trees) = f x trees
当然ながら、この時点で、型は意図したものではない。
*Tree> :t reduceTree
reduceTree
:: (t2 -> List (Tree t2) -> t3) -> t -> t1 -> Tree t2 -> t3
次に、パターンマッチで束縛された変数 trees に対して、データコンストラクタの置き換えを行う。この関数を、とりあえず reduceTree’ としておく。
reduceTree f g z (Node x trees) = f x (reduceList' trees)
where
reduceList' = undefined
変数 trees は、Tree a 型のリストだった。「リスト」なので、データコンストラクタ Nil と Cons の置き換えを考える。以下、reduceList’ 関数の部分だけ見ていく。
Nil の場合は、z と置き換えるだけなので、
reduceList' Nil = z
Cons の場合は、とりあえず、Cons だけ g に置き換える。
reduceList' (Cons tree trees) = g tree trees
変数 tree は、Tree a 型なので、再帰的に reduceTree を適用する。
reduceList' (Cons tree trees) = g (reduceTree f g z tree) trees
変数 trees は Tree a 型のリストなので、これも再帰的に適用する。
reduceList' (Cons tree trees) = g (reduceTree f g z tree)
(reduceList' trees)
これで完成。全体を示す。
reduceTree f g z (Node x trees) = f x (reduceList' trees)
where
reduceList' Nil = z
reduceList' (Cons tree trees) = g (reduceTree f g z tree)
(reduceList' trees)
型を確認する。
*Tree> :t reduceTree
reduceTree
:: (t1 -> t -> t2) -> (t2 -> t -> t) -> t -> Tree t1 -> t2
( cf.jutememo's gist: 1322202 — Gist )
b. 定義済の List a 型の reduceList 関数を利用する場合
ところで、List a 型の「データコンストラクタを置き換える関数」は、既に定義していた。これを利用して reduceTree 関数を定義しなおしてみる。
まずは、変数 trees がリストだったので、これに reduceList 関数を適用する。
reduceTree f g z (Node x trees) = f x (reduceList g z trees)
型を確認したら、
*Tree> :t reduceTree
reduceTree
:: (t -> t1 -> t2) -> (Tree t -> t1 -> t1) -> t1 -> Tree t -> t2
第2引数の、関数の第1引数に、Tree t 型という制約が付いてしまった。(+_+)
そういえば、変数 trees は、Tree a 型のリストだった。よって、リストの要素である Tree a 型の各々の値に対して、reduceTree 関数を適用する必要がある。
reduceTree f g z (Node x trees) =
f x (reduceList g z (mapList (reduceTree f g z) trees))
型を確認する。
*Tree> :t reduceTree
reduceTree
:: (t -> t11 -> t1) -> (t1 -> t11 -> t11) -> t11 -> Tree t -> t1
これで、シンプルに定義することができた。
( cf.jutememo's gist: 1322202 — Gist )
c. reduceTree 関数から map 関数を導く
リストと同じように考えれば、データコンストラクタを利用した値の生成は、reduceTree 関数の引数 f と g と z に、Node と Cons と Nil を与えたものと見ることができる。
よって、与えた木に対して何もせず、そのまま返す関数を定義するには、
idTree = reduceTree Node Cons Nil
Node が持つ値と、Cons が持つ値に、特定の関数を適用する関数を mapTree とするなら、
mapTree f = reduceTree (Node . f) Cons Nil
使ってみる。
*Main> mapTree (* 2) tree
Node 2 (Cons (Node 4 Nil) (Cons (Node 6 (Cons (Node 10 Nil) (Cons (Node 12 Nil) Nil))) (Cons (Node 8 Nil) Nil)))
(cf.jutememo's gist: 1322202 — Gist )
4-2. 木のリストで、データコンストラクタを置き換える関数
上記の木構造において、特定の要素を持つノードを抽出する filter 関数を定義したい。その際、対象となる Tree a 型を、List [Tree a] 型において、要素を1つだけ持つリストであると考えてから、定義を考えたい。
例えば、下図の左の木から、「要素 3 を持つノード以外を抽出したい」とする。 filter 関数の適用により、右のような木になるようにしたい。
また、上記と同じ木から、「ルートである要素 1 を持つノード以外を抽出したい」とする。この場合、右のように、木のリストとして、結果が返されるようにしたい。
ということで、List [Tree a] 型で、filter 関数を考えてみる。
a. 木のリストのデータコンストラクタを置き換える関数
まずは、List [Tree a] 型の、データコンストラクタを置き換える関数を定義してみる。慣れてきたので、一気に置き換える。関数名は reduceListTree とする。
reduceListTree f g z Nil = z
reduceListTree f g z (Cons tree trees) = f (reduceTree g f z tree)
(reduceListTree f g z trees)
( cf.jutememo's gist: 1322202 — Gist )
ところで、List [Tree a] 型は、List a 型の特殊なタイプに過ぎない。ということは、わざわざ reduceListTree 関数を定義する必要はない。List a 型に対して定義した、データコンストラクタを置き換える関数から、導けば良いはず。
Tree a 型のリストに対して、先ほど定義した reduceTree 関数を適用すればいいはずだから、
reduceListTree f g z = mapList (reduceTree g f z)
… と定義したら、思った結果が得られなかった。 (+_+)
上記を修正する前に、Tree a 型の値を、List [Tree a] 型へ変換する関数 tree2ListTree を定義しておく。与えた木を1つだけ、リストの要素として持つようにする。
tree2ListTree tree = Cons tree Nil
List [Tree a] 型の要素に対して、関数を適用する関数を mapListTree とする。
mapListTree f = reduceListTree Cons (Node . f) Nil
使ってみる。
*Tree> mapListTree (* 2) $ tree2ListTree tree
Cons (Node 2
(Cons (Node 4 Nil)
(Cons (Node 6
(Cons (Node 10 Nil)
(Cons (Node 12 Nil) Nil)))
(Cons (Node 8 Nil) Nil)))) Nil
これは上手く動いた。
では、要素を抽出するための filterListTree 関数を定義してみる。
filterListTree p = reduceListTree (\n@(Node x trees) ts ->
if p x then Cons n ts
else trees `appendList` ts)
Node
Nil
動作を試してみる。
*Tree> filterListTree (/= 3) $ tree2ListTree tree
Cons (Node 1
(Cons (Node 2 Nil)
(Cons (Node 5 Nil)
(Cons (Node 6 Nil)
(Cons (Node 4 Nil) Nil))))) Nil
これは、上図の想定通りとなった。しかし、ルートのノードを取り除こうとしたら、
*Tree> filterListTree (/= 1) $ tree2ListTree tree
Cons (Node 1
(Cons (Node 2 Nil)
(Cons (Node 3
(Cons (Node 5 Nil)
(Cons (Node 6 Nil) Nil)))
(Cons (Node 4 Nil) Nil)))) Nil
ルートのノードが残ってしまった。やはり、reduceListTree 関数の定義が間違っている。
そこで、reduceListTree 型を確認すると、
*Tree> :t reduceListTree
reduceListTree
:: (t11 -> t1 -> t1)
-> (t -> t1 -> t11)
-> t1
-> List (Tree t)
-> List t11
reduceListTree 関数を、mapList 関数で定義していたので、結果がリストになってしまっている。つまり、データコンストラクタを置き換える関数にはなっていない。
先ほどの定義を確認する。
reduceListTree f g z = mapList (reduceTree g f z)
reduceListTree 関数は、reduceList の、要素が Tree a 型である特殊な場合であると考えれば、reduceList 関数から、関数を導かなければいけなかった。 (+_+)
まずは、Cons と Nil の置き換えだけを考える。引数 f を Cons に、z を Nil へと置き換えるとする。
reduceListTree f g z trees = reduceList f z undefined
次に、上記で、未定義になっている部分を考える。関数の引数 trees とは List [Tree a] だった。図示すると、
よって、最初に「木」のリストに対して、reduceTree を適用する必要がある。その後、Cons と Nil の置き換えを考えればいい。
reduceListTree f g z trees =
reduceList f z (mapList (reduceTree g f z) trees)
この関数の型のチェックすると、
*Tree> :t reduceListTree
reduceListTree
:: (t1 -> t -> t) -> (t11 -> t -> t1) -> t -> List (Tree t11) -> t
先ほど思った結果にならなかった計算をしてみる。
*Tree> filterListTree (/= 1) $ tree2ListTree tree
Cons (Node 2 Nil)
(Cons (Node 3
(Cons (Node 5 Nil)
(Cons (Node 6 Nil) Nil)))
(Cons (Node 4 Nil) Nil))
これで良さげ。
( cf.jutememo's gist: 1322202 — Gist )
5. 余談： 他の関数を導くための reduce 関数と、畳み込み関数を混同していた
以下、なぜ、くどくどと、この記事を書いたのか、理由を述べる。
最初に引用した、「なぜ関数プログラミングは重要か」を再掲。
… 高階関数は、一度定義すると、非常に簡単に数多くの演算をプログラムすることができる。新しいデータ型を定義したときにその型を処理する高階関数を書くべきである。そうすれば、そのデータ型の取り扱いが簡単になり、その表現の詳細に関する知識を局所化できる。
上記論文では、高階関数の例として、リストとツリーに対して、
- 具体的な計算から、
- 構造の要素が持つ値を集約するための reduce 関数を導く方法
が説明されている。
a. reduce 関数は、畳み込み関数とは違う
高階関数を定義するには、具体的な計算から、共通部分を取り出し、メタ的な関数を導けばよい。以前、上記論文を手本にして、具体的な関数から、抽象的な関数を導く流れを、なぞったことがある。
このとき、念頭に置いていたことは、
- 具体的な計算を、いくつか定義する。
- 似たような計算の形に注目する。
- 類似した計算を共通化できるか考える。その際、関数を与える関数の形で定義。
- 共通化した計算から、具体的な計算を導くことを確かめる。
この手順自体は、共通に使える部品を取り出すための方法としては、ごく普通の考え方。
自分が誤解した点は、高階関数 reduce を、値を集約するための「畳み込み関数」と同じもだと思ってしまったこと。そのため、この記事では、reduce 関数を「畳み込み関数」ではなく、「データコンストラクタを置き換える関数」という視点から捉え直した。
b. 「畳み込み関数」とは
ところで、最初に畳み込み関数を見たのは、Ruby の inject メソッドだった。
例えば、1 から 10 まで足し上げるには、
p (1..10).inject(0){ |x,y| x + y } #=> 55
100 から、1 から 10 までを引いていくと、
p (1..10).inject(100){ |x, y| x – y } #=> 45
最初、複雑に感じたけれど、慣れると for ループが鬱陶しくなる。
Python では、組み込み関数 reduce。
print reduce(lambda x,y: x + y, range(1,11), 0) #=> 55
print reduce(lambda x,y: x - y, range(1,11), 100) #=> 45
Hakell では fold。foldr と foldl では、計算の方法が異なる。(cf. Haskell の foldl , foldr )
*Main> foldr (+) 0 [1..10]
55
*Main> foldl (-) 100 [1..10]
45
上記の通り、畳み込み関数は、「リストの要素に対して、任意の二項演算子で、値を順にまとめ上げていく」ために利用できる。
そのため、「reduce = 畳み込み関数」という構図で記憶してしまった。
c. リストの foldr の定義により混同した
上記の通り、Haskell で、畳み込み関数と言えば、リストに対する fold 系の関数。
- foldl :: (a -> b -> a) -> a -> [b] –> a
- foldr :: (a -> b -> b) -> b -> [a] -> b
「なぜ関数...」で定義されている reduce 関数と、Haskell の foldr は似ている。しかし、Haskell の foldr, foldl は、その名前の通り、要素の値を「畳み込み、集約する」目的で定義しているように見受けられる。（理由は、リストが Data.Foldable のインスタンスとなっているため。また、Data.Tree も同インスタンスとして定義されており、あくまでも、値を畳み込むために使うのが、fold の役割だと思う。）
これに対し、「なぜ関数...」で解説されている reduce 関数は、要素の値を畳み込む用途にも使えるという点が異なる。「畳み込みこと」自体が目的ではない。畳み込むことは、用途の一例に過ぎない。
ただし、リストは、Haskell の foldr と 、論文中の reduce の定義が同じになるため、データコンストラクタを置き換える関数を、畳み込み関数と更に混同してしまった。
d. その型を処理する高階関数を何と呼ぶべきか？
引用した文章の中に、
新しいデータ型を定義したときにその型を処理する高階関数を書くべきである。
と述べられている。繰り返しになるが、これは、「畳み込み関数」を定義することを意味しない。
「畳み込み関数」は、高階関数の一例であり、必ずしも、対象の型を処理するための関数を導くことができる、柔軟な関数ではない。しかし、先ほど述べたように、リストの場合は、畳み込み関数を元にして、いくつかの関数を導くことができる。
では、「その型を処理する高階関数」とは何と呼べばいいのだろうか？
適切な言葉見つからなかったので、自分はこれに対して、
データコンストラクタを置き換える関数
もしくは、
データコンストラクタが保持している値を、データコンストラクタの縛りから解放する関数
と呼ぶことにした。こうすれば、自分の中で、畳み込み関数と混同しないで済む。
もちろん、「なぜ関数...」で、reduce 関数を、「畳み込み関数」とは述べていない。また、reduce 関数を「データコンストラクタを置き換えると考えれば良い」との解説もあった。しかし、最初読んだとき、その意味がわからず、「畳み込む」関数を定義することが、「その型を処理する高階関数」 を定義することに相当すると誤解した。
e. fold, reduce の言葉の意味について
ところで、Haskell で畳み込み関数として使われている `fold’ の単語の意味を調べると、
foldの意味 - 英和辞書 - goo辞書
1 … 〈薄い物を〉折る, 折り重ねる((in, over, together))；…を（きちんと）折りたたむ((down, up))；…を折り返す((back))；…をたたんで（…に）する((into ...))；…を折りたたんでかたづける((away)). ⇒BEND1(他)1
fold a sheet of paper small ［in thirds］
紙を小さく［3つに］折る.
fold - Definition with thesaurus
1. a. to bend or press (something) so that one part is over another; double up on itself: to fold a sheet
これより、「折り重ねる」というイメージの言葉だとわかる。ちなみに、この「折り重ねる」という意味で、fold がより一般化された形で定義されているのが Data.Foldable らしい。
これに対して、reduce について調べると、いくつか意味が書かれている。この場合、適切だと思われるのは、
reduceの意味 - 英和辞書 - goo辞書
(2) 〈A（物・事）をB（別の状態・単純な要素）に〉する, 変える, 分解する, 変形する
reduce grapes to wine
ブドウをワインにする.
reduce - Definition with thesaurus
4. a. to put into a different form: to reduce a talk to writing
b. to change to a different physical form, as by melting, crushing, grinding, etc.
こちらは、「分解して、変形させる」というイメージ。
「データコンストラクタを置き換えて、別の値にする」という役割に対しては、このニュアンスが相応しい。
f. reduce 関数を理解するために重要な点
「なぜ関数...」には、リストに対する関数 reduce の定義の方法に関して、重要なことが次のように書かれている。
(reduce f a)を理解する一つの方法は、リストのなかで、consが出現するところをすべてfで置換え、nilが出現するところをすべてaで置換える関数だと看倣すことである。
同様のことが、ツリーに対する redtree 関数の定義の仕方に関して、以下のように記述されている。
ツリーはnodeと consとnilで組み立てられているので、redtreeはそれぞれを置換える何かという三つの引数をとらなければならない。ツリーとリストは別の型なので、それぞれの型の上の演算に一つずつ、二つの関数を定義する必要がある。
先ほど述べたように、この部分を初めて読んだとき、どういう意味なのかわからなかった。特に、ツリーの redtree 関数を定義するのに、「なぜ、具体的な計算を考えないで導くことができるのだろう？」と疑問を感じた。
そのため、自分で「なぜ関数...」を手本にして、例をなぞったとき、以下のように、具体的な計算を考えてから、redtree 関数を定義した。
-
-
-
これにより、確かにツリ－の redtree 関数では、リストの reduce 関数とは違い、与える引数の数が 1 つ多くないと、maptree 関数を定義できないことが理解できた。振り返ってみると、このとき、redtree 関数の定義の仕方について、明確に意識しておくべきことがあった。それは、先ほどから何度も述べているように、データコンストラクタに注目すること。ポイントは、
データコンストラクタを一関数とみなし、それを可換とする関数を定義する
と考えること。この視点があれば、 reduce は複雑な定義でない。
先ほど、 reduce の言葉の意味が
「分解して、変形させる」というイメージ
に対応すると述べた。それは、データコンストラクタを置き換え、全く別の型の値にしてしまうという操作が、「分解して、変形させる」ことに対応していると感じたため。
g. reduce 関数とは何か？
ところで、時は過ぎ、reduce 関数の定義を忘れ、「畳み込み」という言葉だけが、頭に残った。
そして、「畳み込む」手段として、
2 つの要素に関数を適用して、一つの値に集約していく「二項演算子」をどう定義すればいいのか？
という問題を考えることが、「新しい型を定義したときに、定義すると便利な高階関数」を導く手段だと、勘違いするようになっていた。
今考えると、「畳み込む」という言葉のイメージに流されたのがいけなかった。
今では、関数 reduce を、
データコンストラクタが保持している値を、データコンストラクタの縛りから解放する関数
と考えるようになった。そうすれば、具体的な計算から、抽象的な計算を導く過程を考えずに済む。
「何を何で置き換えればいいのか？」
だけに注目すればいい。
このような役割を持つ reduce 関数って、一体何だろう？普通のオブジェクト指向の言語で例えるなら、既存のオブジェクトを、そのオブジェクトが持っている情報を元に、別のクラスに鞍替えさせるようなものかな？
