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)
|
カテゴリ
新型コロナウイルス 主インデックス Haskell 記事リスト 圏論記事リスト 考えるということのリスト 考えるということ ラッセルのパラドックス Haskell Prelude Ocaml ボーカロイド 圏論 jQuery デモ HTML Python ツールボックス XAMPP Ruby ubuntu WordPress 脳の話 話のネタ リンク 幸福論 キリスト教 心の話 メモ 電子カルテ Dojo JavaScript C# NetWalker ed と sed HTML Raspberry Pi C 言語 命題論理 以前の記事
最新のトラックバック
最新のコメント
ファン
記事ランキング
ブログジャンル
画像一覧
|
ファン申請 |
||