人気ブログランキング | 話題のタグを見る

RWH の読み方(34) 第4章

Real World Haskell 第4章 Functional Programming

The Left Fold

このサブセクションでは前の Computing One Answer over a Collection で作成した Adler-32 チェックサムのプログラムを左畳込み関数の foldl を使って書きなおしている。

このサブセクションを理解するためには、2つのことを理解している必要がある。まず、Adler-32 とは何かということ、もうひとつはなぜ「畳込み」を理解する必要があるのかということだ。

そこで、順番は逆になるがまず、「何で畳み込みが必要なのか」ということを考えてみる。

Haskell のリスト操作関連の高階関数の動作にはびっくりするような物がたくさんある。例えば map だ。第1引き数にリストの要素に適用したい関数を与えると、リストの全ての要素にそれぞれ関数適用した新しいリストを値として返してくれる。

Prelude> map (*2) [1,2,3,4,5]
[2,4,6,8,10]
Prelude> map (^2) [1,2,3,4,5]
[1,4,9,16,25]

これらは、本来はループを使って記述するプログラムだ。例えば、リストの要素を2倍にするプログラムは次のようになる。

double [] = []
double (x:xs) = (x * 2) : double xs

ghci で確認すると次のようになる。

Prelude> let double [] = []; double (x:xs) = (x * 2) : double xs
Prelude> double [1,2,3,4,5]
[2,4,6,8,10]

リストの要素の二乗を求めるプログラム square は次のようになる。

square [] = []
square (x:xs) = (x ^ 2) : square xs

この square と先ほどの double はプログラムの形が非常に似ているつまり次のような形をしている。

func [] = []
func (x:xs) = (f x) : func xs

square と double は先頭の要素に適用する関数 f が違っているだけだ。それなら f を引き数として与えることでこのループそのものを関数にしてみたらどうだろう。

myMap f [] = []
myMap f (x:xs) = (f x) : myMap f xs

これも ghci で試してみた。

Prelude> let myMap _ [] = []; myMap f (x:xs) = (f x) : myMap f xs
Prelude> myMap (*2) [1,2,3,4,5]
[2,4,6,8,10]

驚いたことに、Haskell はこのように「形の似たプログラム」という抽象的なものも関数にしてしまうことができる。

それでは「畳込み」についてはどうだろうか。

「畳込み」の関数 foldr や foldl を始めて使ってみたときは、何のことかさっぱり分からなかった。foldr を使うと sum や product と同じことができるのは分かるが、だからどうなのという気がした。ちなみに、sum や product の動作を forldr でさせると次のようになる。

Prelude> foldr (+) 0 [1,2,3,4,5]
15
Prelude> foldr (*) 1 [1,2,3,4,5]
120

これだけでは、sum や product をわざわざ複雑にしただけでなにがありがたいのかということになる。

しかし、これも map のときと同じで、「似た形のループ」という抽象的な概念を関数にしたものだと考えるとその意味が分かる。たとえば、sum と product のプログラムは次のようになる。

sum [] = 0
sum (x:xs) = x + sum xs

product [] = 1
product (x:xs) = x * product xs

上の2つのプログラムの共通部分を関数にすると次のようになる。

myFoldr f zero [] = zero
myFoldr f zero (x:xs) = x `f` (myFoldr f zero xs)

これも ghci で試してみることができる。

Prelude> let myFoldr _ zero [] = zero; myFoldr f zero (x:xs) = f x (myFoldr f zero xs)
Prelude> myFoldr (+) 0 [1,2,3,4,5]
15

このように「畳込み」関数とはループという抽象的な操作を関数に落とし込んだものだと考えるとそのありがたみが分かる。また、foldr の動作はそのシミュレーションを手書きでやってみると理解できる。

foldr (+) 0 [1,2,3]
= 1 + (foldr (+) 0 [2,3])
= 1 + (2 + (foldr (+) 0 [3]))
= 1 + (2 + (3 + (foldr (+) 0 [])))
= 1 + (2 + (3 + 0))
= 6

また、foldr の動作は直接機械に教えてもらうこともできる。

Prelude> foldr (\x y -> concat ["(",x,"+",y,")"]) "0" (map show [1..5])
"(1+(2+(3+(4+(5+0)))))"

foldl の解釈は foldr より少し複雑になるので稿を改めるが、ここで、なぜ畳込みが必要かということについて考えてみたい。ループを畳み込みに置き換えることでどのような利点が発生するのだろうか。

それは、ループを folds に置き換えることでそのループの性質を明示することができるということだ。つまり、map を使った時と foldr を使ったときは異なる種類のループを使っていることを意味している。どんな性質のループを使っているのかを意識しながら使うことができるということだ。

もうひとつは明示的にループを書くよりも簡潔になり可読性を上げタイポを減らすことができる。

いろいろな意味で、リストから単一値を求めるようなプログラムでは、積極的に folds を使う理由がある。
by tnomura9 | 2012-04-16 07:56 | Haskell | Comments(0)
<< 土岐麻子 踊ってみた美女図鑑 >>