Haskell のデータ構造と高階関数 - 総和・総乗から畳み込み関数へ

1. ウォーミングアップ用の課題を作成

久しぶりに Haskell を触ったら、毎度のごとく、頭から抜けてる。。 (o_ _)ｏ~† 以前の記事を読み返しても、他人が書いたものにしか見えない。 (@_@;

どんな言語でも、一定期間、手を動かしてないと、基本的なことですら忘れる。

関数を定義する構文って def で始まるんだっけ？それとも function だったかな？

変数定義するとき、何を前に書くんだっけ？

など枚挙にいとまがない。だから、関数名なんて、色々なものがごちゃ混ぜになり、覚える気さえ起きない。

言語の依って立つパラダイムに馴染んでないと、そんな表層的な部分だけでなく、根本的なところでわからなくなる。覚えたと思ったことが、その片鱗さえ消え去っていることは日常茶飯事。そして、意気消沈。 1 歩進んでは 2,3 歩後退し、何かの間違えで、偶然 1 歩進める。そんな繰り返し。

当の Haskell は、相変わらず停滞している。どこまで何を理解したか、記憶が定かでない。さすがにこれではまずい。

対策として、思いついたのは計算ドリル。小学生のとき、機械的に計算を繰り返すことにより、計算に慣れた。それと同じように、ウォーミングアップ用の課題を用意しておき、記憶の底に沈み込んだ感覚を、少しでも回収できるよう、自分用の課題を用意しておくことにした。

2. 課題の内容

今回、課題としたのは、関数型プログラミングを学ぼうとした契機となった論文の一つより抽出。

「なぜ関数プログラミングは重要か」の「3. 関数の貼り合せ」

の部分。この節は特に、関数の抽象化に馴染むための題材として打って付け。 Haskell に限らず、関数を引数として渡せたり、関数の返り値として関数を返すことができる言語、所謂、関数がファーストクラスオブジェクトな言語の練習課題として良いはず。

課題の内容は、

リスト型を定義
リストの要素に対して、「総和・総乗」を求める関数を定義 … (A)
(A) の関数を元にして、抽象化した畳み込み関数を定義
上記の畳み込み関数を使って以下を定義
- 総和・総乗
- 値をコピーする関数
- 要素に関数を適用する関数 ( map )
- 特定の要素を抽出する関数 ( filter )

上記と同様な課題を、ツリーに対しても行う。

まとめると、

代数的データ型を定義し
簡単な計算を行ない
そこから高階関数を導き
高階関数を使って、他の関数を定義する

3. リストで総和・総乗から、畳み込み関数まで

a. リストを代数的データ型で定義

まずはリストを定義する。 Haskell ではリストに対して特別な構文が用意されているが、ここでは代数的データ型として自分で定義する。 (cf. 6.1.3 リスト, Haskell の cons ) その方が、後々、別のデータ型を定義したときの参考になるため。

データコンストラクタは、以下の二つから成る。

空のリストを表わす Nil
リスト型の先頭に要素を追加するデータコンストラクタ Cons

data List a = Nil 
            | Cons a (List a)
              deriving Show

これを用いて、例えば、数値 1 ~ 4 の要素を持つリストを作成。

list0 = Cons 1 (Cons 2 (Cons 3 (Cons 4 Nil)))

b. リストで総和、総乗の定義

次に、リストの要素の総和を返す sumList 関数の定義をしてみる。

sumList Nil = 0
sumList (Cons x xs) = x + sumList xs

これに対して、総乗を返す関数 productList の定義は、

productList Nil = 1
productList (Cons x xs) = x * productList xs

先ほど定義した変数、リスト list0 に対して、上記の関数を適用すると、

main = do print $ sumList list0      -- 10 
          print $ productList list0  -- 24

c. リストで畳み込み関数

上記二つの関数の形は、よく似ている。違いは以下の具体的な値と関数。

リストが空のときの値
値を畳み込むための二項演算子

よく似た処理があるなら、それをまとめたい。そのためには、上記二つを「引数」として与える関数を考えれる。この関数を reduceList という名前にするなら、次のように定義できる。

reduceList f z Nil = z
reduceList f z (Cons x xs) = x `f` reduceList f z xs

元の関数から、引数を増やし、具体的な関数を、引数で与えた関数で置き換えるだけ。

この関数を用いて先ほどの総和と総乗を再定義すると、

sumList'     = reduceList (+) 0
productList' = reduceList (*) 1

d. 畳み込み関数を利用してリストを返す

総乗・総和の計算は、二項演算子を手段として、要素を一つの値に畳み込み集約する。一つの値に集約できるのは、二項演算子 (+), (*) の型を見ればわかる。

*Main> :t (+)
(+) :: (Num a) => a -> a -> a
*Main> :t (*)
(*) :: (Num a) => a -> a -> a

数値と数値を足し合わせたり、掛け合わせると、結果が数値になるため。

ところで、リスト型を定義したときのデータコンストラクタは、

要素
リスト

の二つを引数に与えると、リストが生成される二項演算子だった。データコンストラクタの型を確認すると、

*Main> :t Cons
Cons :: a -> List a -> List a

第 1 引数と第 2 引数の型が異なることがわかる。

データコンストラクタは、普通の関数と同じようなもの。(+), (*), Cons を中置記法で書いて比較すると、

*Main> 1 + 2
3
*Main> 1 * 2
2
*Main> 1 `Cons` Nil
Cons 1 Nil

データコンストラクタ Cons は、 (+) や (*) とはちょっと赴きが違うけれど、同じ仲間であることが、形の上ではっきりとする。ということは、総和・総乗を reduceList で定義したときと同じように Cons を reduceList へ与えても問題ない。

では、Cons を reduceList の第1引数として渡した場合、第2引数には何を渡せばいいのだろうか？

reduceList の計算のイメージを List folds as structural transformations を元に、第1引数に (+), 第2引数に 0 を与えた場合で考えたのが下図。

これに対して上図の (+) の代わりに Cons を渡した場合、右端に置ける値は何か？

先ほど Cons の型を確認したときのことを思い出せば、

*Main> :t Cons
Cons :: a -> List a -> List a

上記 `？’ の場所には List a 型の値を置けることが見てとれる。

reduceList 関数において、これで問題ない理由は、Cons の第2引数と返り値の型が同じであるため。

ところで `？’ に Nil が来れば、与えたリストの要素をそのまま返す copyList 関数が定義できる。

copyList = reduceList Cons Nil

Nil ではなく Cons 1 (Cons 2 … のようなリストが来たなら、リストをリストに追加する appendList が定義できる。

appendList xs ys = reduceList Cons ys xs

もちろん、reduceList 関数を使わなくても、以下のように定義できる。

appendList' Nil xs         = xs
appendList' (Cons x xs) ys = Cons x (appendList' xs ys)

e. 要素に関数を適用する map 関数

「なぜ関数プログラミングは重要か」では、reduce 関数から map 関数を導くまで、丁寧に描かれている。ここでは、そこはすっ飛ばし、関数を合成する関数 compose を定義する。

compose f g h = f (g h)

この関数を使った、以下のような計算を考える。

compose Cons (* 2)

この式の型は、

*Main> :t compose Cons (* 2)
compose Cons (* 2) :: (Num t) => t -> List t -> List t

第 1 引数に数値、第 2 引数にリストを与えるとリストが返される。例えば、

*Main> (compose Cons (* 2)) 1 Nil
Cons 2 Nil

よって、compose の第2引数に関数を与える形にして、 reduceList の第1引数に与えることで map 関数が導かれる。

mapList f = reduceList (compose Cons f) Nil

mapList 関数を試してみる。

print $ mapList (* 2) list0 -- Cons 2 (Cons 4 (Cons 6 (Cons 8 Nil)))

もちろん、reduceList を使わなくても、map 関数は以下のように定義できる。

mapList' f Nil         = Nil
mapList' f (Cons x xs) = Cons (f x) (mapList' f xs)

f. 要素を抽出する filter 関数

map 関数が定義できたので、次は filter 関数。

ここでは、できるだけ Haskell で用意されている構文を使わないで書いてみたい。そこで、予め if を関数として書いておく。 (cf. if と真偽値 )

if' True  x _ = x
if' False _ y = y

これを用いて、要素を判定する述語を第1引数として与える関数 filterList を定義。 ( cf. 述語 )

filterList p = reduceList filter' Nil
    where
      filter' e l = if' (p e) (Cons e l) l

例えば、2 で割れる要素だけ抽出したい場合は、

print $ filterList (\x -> x `mod` 2 == 0) list0

こちらも map と同じく reduceList を使わずに定義するなら、

filterList' p Nil         = Nil
filterList' p (Cons x xs) = if' (p x) (Cons x filter') filter'
    where
      filter' = filterList' p xs

4. ツリーで総和・総乗から、畳み込み関数まで

リストの場合と同じように、ツリーでも以下の流れを踏襲して定義する。 ( filter だけちょっと違うけれど。)

ツリー型を定義
ツリーの要素に対して、「総和・総乗」を求める関数を定義 … (A)
(A) の関数を元にして、抽象化した畳み込み関数を定義
上記の畳み込み関数を使って以下を定義
- 「総和・総乗」を再定義
- 値をコピーする関数を定
- 要素に関数を定義する関数を定義 ( map )
特定の要素を抽出する関数を定義 ( filter )

a. ツリーを代数的データ型で定義

最初は、ツリーの代数的データ型を定義。

ここで、ツリーは各値を持つノードから成り、ノードはツリーのリストを持つとする。(「なぜ関数プログラミングは重要か」に書かれていたのと同じ形にした。)

data Tree a = Node a (List (Tree a))

これを用いてツリーの値を作成してみる。

tree0 = Node 1 
        (Cons (Node 2 
               (Cons (Node 10 Nil) 
                (Cons (Node 20 Nil) 
                 Nil)))
         (Cons (Node 3 Nil) 
          (Cons (Node 4 Nil) 
           Nil)))

上記の表現だと、全体を把握しにくいので、Tree a 型を Show クラスのインスタンスにして、print 関数で出力したときに見やすく整形して出力されるようにしておく。

instance (Show a) => Show (Tree a) where
    show (Node x Nil) = show x
    show tree0        = show' tree0 0
        where
          show' (Node x trees) n = tabs   ++ 
                                   show x ++ 
                                   showTrees' trees (n+1)
              where
                tabs = replicate n '\t'

                showTrees' Nil n                = ""
                showTrees' (Cons tree1 trees) n = "\n"          ++ 
                                                  show' tree1 n ++ 
                                                  showTrees' trees n

これにより先ほどのツリーは、

*Main> tree0
1
	2
		10
		20
	3
	4

と表示される。

b. ツリーで総和、総乗の定義

リストの時と同じように、総和と総乗を定義する。

ノードが保持する値が数値であるとして、ツリー全体の「総和」を求めるには、

sumTree (Node x trees) = x + sumTree' trees
    where
      sumTree' Nil               = 0
      sumTree' (Cons tree trees) = sumTree tree + sumTree' trees

これに対して「総乗」は、

productTree (Node x trees) = x * productTree' trees
    where
      productTree' Nil               = 1
      productTree' (Cons tree trees) = productTree tree * productTree' trees

上記 2 つの関数を試してみる。

print $ sumTree tree0      -- 40
print $ productTree tree0  -- 4800

c. ツリーで畳み込み関数 (1)

リストの場合と同じく、畳み込み関数を定義する。ただし、ここでは、ツリーのリストを畳み込むための関数と、その結果となる値と、ツリーのノードを畳み込む関数を、同じもので定義してみる。

reduceTree f z (Node x trees) = x `f` reduceTree' f z trees
    where
      reduceTree' _ z Nil         = z
      reduceTree' f z (Cons t ts) = reduceTree f z t `f` reduceTree' f z ts

これを用いて総和と総乗を再定義。

print $ reduceTree (+) 0 tree0
print $ reduceTree (*) 1 tree0

d. ツリーで畳み込み関数 (2)

次に、ツリーの要素に対して何もせず、元のツリーの値を返す関数の定義を試みる。リストのときと同様に考え、reduceTree にツリーのデータコンストラクタを渡せば…

copyTree = reduceTree Node Nil

… としてはダメ。これでは、ツリーをコピーすることができない。理由は上記の定義で、敢えて関数を適用した後の値を書くとするなら、以下のようなツリーを構築しようとしているため。

tree0 = Node 1 
        (Node (Node 2 
               (Node (Node 10 Nil) 
                (Node (Node 20 Nil) 
                 Nil)))
         (Node (Node 3 Nil) 
          (Node (Node 4 Nil) 
           Nil)))

これは、明らかにツリーではない。

ツリーの型は、以下のように、

data Tree a = Node a (List (Tree a))

データコンストラクタ Node と、リストのデータコンストラクタから構成されている。よって reduceTree は高階関数として、もう一つデータコンストラクタを受け取る引数を用意しなければならない。

reduceTree f g z (Node x trees0) = x `f` reduceTree' f g z trees0
    where
      reduceTree' _ _ z Nil                 = z
      reduceTree' f g z (Cons tree1 trees1) = reduceTree  f g z tree1 `g` 
                                              reduceTree' f g z trees1

これを使い元のツリーをそのまま返す関数は、

copyTree = reduceTree Node Cons Nil

と定義できる。

総和・総乗を定義するなら、

print $ reduceTree (+) (+) 0 tree0
print $ reduceTree (*) (*) 1 tree0

e. 要素に関数を適用する map 関数

全てのノードの保持する値に関数を適用するには、ノードの値に関数を適用できるようにすればよい。よって、畳み込み関数の第1引数に、Node と与えた関数を合成したものを与える。

mapTree f = reduceTree (compose Node f) Cons Nil

試してみる。

*Main> mapTree (* 2) tree0
2
	4
		20
		40
	6
	8

f. filter (1) – ツリーからリストに変換した後に抽出する方法

では、要素を抽出するための filter はどうやって定義できるのだろう？うーん… (@_@;

ところで、「ふつうのHaskellプログラミング」(p122) には、Haskell で採用されている「遅延評価」について、次のように述べられている。

評価しなければならない値が存在するとき、実際の計算を値が必要になるまで行わない

( 遅延評価 - Wikipedia より )

また、Haskell で代表的なデータ型である「リスト」については、「インターフェイスを統一できる」利点があるとして、次のように述べられている。

例えば巨大なツリー構造の全要素を順番にアクセスしたいと考えてみてください。Java で書くなら、ツリーに対するイテレータを用意するでしょう。一方Haskell の場合には、ツリーの要素すべてを含むリストを返す flatten という関数が使われます。

Haskell で用意されている Data.Tree 型を見ると、

flatten :: Tree a -> [a]

という関数が定義されており、返り値はリスト。

リストが遅延評価される Haskell ならば… ツリーの要素をすべて集める flatten 関数を使っても、本当にリストが生成されるのはリストを初めてたぐったときです。 flatten 関数を使ったリストが生成されることはありません。

(同上より)

「Scheme:オブジェクト指向表現」では、「ツリーの要素を辿って関数を適用するコード」が紹介さている。これに対しても、Haskell の遅延評価の観点から次のようなコメントがされている。

tree のトラバースは、要するに与えられた tree のすべてのノードを一列のリストにならべればよいわけです。

「Haskell プログラミング ∼ 純粋関数型言語への誘い∼」 (p.28) には「Haskell のパターン」として、次のように書かれている。

代数データ型を定義する
そのデータ型を走査する高階関数を書く
高階関数に条件を指定し、必要な部分をリストにする
リストになれば、何でもあり

以上より、ツリーをリストにする関数 flatten を定義してみる。

flatten (Node x trees0) = Cons x (flatten' trees0)
    where
      flatten' Nil                 = Nil
      flatten' (Cons tree1 trees1) = flatten  tree1  `appendList` 
                                     flatten' trees1

この関数と、先ほどリストで定義したフィルタ関数を合成して、以下のように定義できる。

filterTree2List p = filterList p . flatten

この関数を使ってみる。

*Main> filterTree2List (\x -> x `mod` 2 == 0) tree0
Cons 2 (Cons 10 (Cons 20 (Cons 4 Nil)))

g. flatten の定義でリストの畳み込み関数を使う

ところで、Haskell で用意されている Data.Tree 型の flatten 関数の定義を見ると、畳み込み関数 foldr が使われている。

flatten :: Tree a -> [a]
flatten t = squish t []
  where squish (Node x ts) xs = x:Prelude.foldr squish xs ts

一見したところ、何でこれで定義できるのかわからなかった。。 (@_@; 特に squish 関数の定義の中で、畳み込み関数を使っており、その第 1 引数に squish を与えるところがイメージできない。

頭の中でイメージできないときは、図を描きながら考えてみる。まず、squish 関数の中の xs は、最初に空リストを与えられて呼出されていることより、リストであることがわかる。 ts は Tree a 型のデータコンスラクタの定義より [Tree a] 。よって、先ほどのように畳み込み関数をツリー状にして考えるなら、以下の図のようになる。

最初に、右下端の二項演算子を適用する部分に注目。この二項演算子の引数は、squish の定義で見たように第1引数は Tree a 型の値で、第2引数は空リスト。

ところで、定義の 1 行目は以下のように記述されている。

flatten t = squish t []

squish は flatten と比較すると引数が一つ追加され、具体的な値が与えられていることより、

flatten は汎用的な squish 関数の特殊なケース

であることが読み取れる。

しかし、なぜ flatten が squish の特殊ケースとして定義できるのだろう？上図の青い点線で囲ったところを意識しながら見るとわかるかもしれない。 flatten t が t をリストに変換することに対して、squish t [] は t をリストに変換したものに対して空リストを追加している。つまり、両者は同じ結果を返すことが明白 (？) QQQ

それにしても、どうして上記のような定義ができることを思い付いたのか理解できない。(+_+)

関数を定義するときに、

「この関数はどういった汎用的な関数の特殊ケースであるか？」

ということを常に考えていればいいのだろうか…。

この点に関して、とりあえず横に置いておき、先ほどの flatten を畳み込み関数を使って定義しなおしてみる。

flatten (Node x trees0) = Cons x (reduceList flatten' Nil trees0)
    where
      flatten' tree1 xs = flatten tree1 `appendList` xs

うーん…、動作はするけれど定義の仕方が異なる。 (+_+)

ここで flatten’ の第1引数をデータコンストラクタによるパターンマッチに変更し、上記の appendList 関数を使わず Cons で書いてみる。

flatten (Node x trees0) = Cons x (reduceList flatten' Nil trees0)
    where
      flatten' (Node x tree1) xs = Cons x (reduceList flatten' xs tree1)

上記の太字の部分を見比べると、

Cons x (reduceList flatten' Nil trees0)

は、

Cons x (reduceList flatten' xs tree1)

の特殊なケースであることがわかる。

よって、これをまとめ、最終的に以下のように定義ができるということだったのかな？

flatten (Node x trees0) =  flatten' tree0 Nil
    where
      flatten' (Node x tree1) xs = Cons x (reduceList flatten' xs tree1)

h. filter (2) - なるべくツリーの形を保って要素を抽出

先ほどはツリーをリストに変換してから要素を抽出した。別の抽出方法として、ある程度ツリーの形を保ったまま抽出ではできないだろうか？

例えば以下のようなツリーがあった場合、

奇数の要素のみを抽出した結果は、

1
	3

偶数の要素を抽出した結果は、

というような関数を定義したい。

返される値は、ツリーが一つのこともあれば、ツリーのリストであることもある。関数名を filterTree とするなら、Tree a 型の値と要素を抽出するための述語を与えたら、Tree a 型の値のリストを返せばいいので

filterTree :: (a -> Bool) -> Tree a -> List (Tree a)

何も考えずにだらだらと定義すると…

filterTree :: (a -> Bool) -> Tree a -> List (Tree a)
filterTree p (Node x trees0) 
    | p x  == True = Cons (Node x trees') Nil
    | otherwise    = trees'
    where
      trees' = filterTree' trees0
          where
            filterTree' Nil                 = Nil
            filterTree' (Cons tree1 trees1) = filterTree p tree1 
                                              `appendList` 
                                              filterTree' trees1

せっかくなので、畳み込み関数で置き換えると、

filterTree p (Node x trees0) 
    | p x  == True = Cons (Node x trees') Nil
    | otherwise    = trees'
    where
      trees' = reduceList filter' Nil trees0
          where
            filter' tree xs = filterTree p tree `appendList` xs

ここから、Data.Tree 型の flatten 関数の定義と同じように、より汎用的な関数の特殊な形という形式に定義を置き換えることはできるだろうか？

上記の tree’ をインライン化し、filter’ 関数の第1引数をデータコンストラクタによるパターンマッチに置き換えると次のようになる。

filterTree p (Node x trees0) 
    | p x  == True = Cons (Node x $ filterTree' trees0) Nil
    | otherwise    = filterTree' trees0
    where
      filterTree' = reduceList filter' Nil
          where
            filter' (Node x trees1) xs 
                | p x == True = Cons (Node x $ filterTree' trees1) xs
                | otherwise   = filterTree' trees1 `appendList` xs

よく見ると、上部の太字の定義は、下部の太字の定義の特殊なケースであることがわかる。

よって、これをまとめると以下のように書ける。

filterTree p trees0 = filter' trees0 Nil
    where
      filter' (Node x trees1) xs
          | p x  == True = Cons (Node x $ filterTree' trees1) xs
          | otherwise    = filterTree' trees1 `appendList` xs
          where
            filterTree' = reduceList filter' Nil

上記の関数を使う前に List a 型の導出インスタンス宣言を削除し、出力の方法を変える。

instance (Show a) => Show (List a) where
    show Nil          = ""
    show (Cons x Nil) = show x
    show (Cons x xs)  = show x ++ "\n" ++ show xs

試してみる。

*Main> filterTree (\x -> x `mod` 2 /= 0) tree0
1
	3
*Main> filterTree (\x -> x `mod` 2 == 0) tree0
2
	10
	20
4

すぐに忘れる脳みそのためのメモ

2010年7月21日水曜日