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

RWH の読み方(37) 第4章

Real World Haskell 第4章 Functional Programming

Why Use Folds, Maps, Fiters

このサブセクションでは、前節の alder32_foldl が adler32_try2 と比べてもさほど短くならなかったのに、なぜ folds を勧めるのかを説明している。

その理由のひとつは、foldl や foldr と同じパターンの再帰関数は Haskell に非常に多く出現するので、folds の使い方に慣れておけば、明示的な再帰関数を読解するより読解が容易になるということだ。

もうひとつの理由は folds を使うことで再帰関数の性質が明確になり、コンパクトで信頼性のあるコードが書けるようになるということだ。

これは、map や filter でも同様に言えることで、高階関数を一度覚えると後はいろいろな状況でそれを利用できるようになる。

ここからは、管理人の意見。

folds や map, filter などの高階関数は、データの処理そのものを扱うのではなく、ある処理を行うにはこういうプログラミングの型を使うというような抽象的な手順を道具として使うことを可能にしている。

そのため、最初は抽象的で理解が難しいが、一旦理解するとあらゆるプログラミングに応用できて、コードも劇的にコンパクトになる。なにしろ、ループを記述しないといけないような処理を一行で片付けてしまうからだ。もちろん可読性も大いに上がる。

たたし、map や filter の動作は比較的理解しやすいが。folds の理解はどうしたらいいのだろうか。

それは、前節で述べたように、foldr は右再帰型の汎用再帰関数で、foldl は左再帰型の汎用再帰関数と考えればいいのだ。

右再帰型とか、左再帰型とかいうのは、構文解析の理論で使われる用語で再帰関数に流用していいかどうかは知らないので注意してほしい。しかし再帰関数をこの様に分類することで foldr と foldl の使い分けが明確になる。

たとえば、リストの要素を合計する関数 sum の再帰的定義は次のようになる。

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

この関数が実際に使用された時の式の展開の様子は次のようになる。

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

このような、再帰関数では関数の再帰的な展開が右へ右へと行われていくそのため、このタイプの再帰関数を右再帰型と呼ぶことにする。この右再帰型の再帰関数は機械的に foldr に翻訳することができる。

つまり、演算 (+) を foldr の第1引き数に、sum の the base case の値 0 を foldr の第2引き数に、sum の引き数のリストを foldr の第3引き数にすればいいのだ。

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

foldr の式の展開を機械に聞くと次のようになる。

Prelude> foldr (\x y -> concat ["(",x," + ",y,")"]) "0" ["1","2","3"]
"(1 + (2 + (3 + 0)))"

この右再帰型の再帰関数は、リストの先頭から要素を順次取り出して処理するが、リストの最後から要素を順次取り出す計算もある。例えば [1..n] の階乗を計算するときは、大きい数の n の方から取り出して順に乗算を繰り返していく。

階乗の計算のように、リストの末尾から要素をとりだすパターンは Haskell にはないが、仮想的に (xs:x) というパターンが利用可能であるとする。すると階乗の計算のプログラムは次のようになる。

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

これを、リスト [1,2,3] に展開したものは次のようなる。

fact [1,2,3]
= (fact [1,2]) * 3
= ((fact [1]) * 2) * 3
= (((fact []) * 1) * 2) * 3
= ((1 * 1) * 2) * 3
= 6

再帰関数の展開が左へ左へと進んでいくので左再帰型の再帰関数と呼ぶことにする。

このタイプの再帰関数は foldl に翻訳できるのだ。次のように foldl を展開していけば理由がわかる。

foldl (*) 1 [1,2,3]
= foldl (*) (1 * 1) [2,3]
= foldl (*) ((1 * 1) * 2) [3]
= foldl (*) (((1 * 1) * 2) * 3) []
= (((1 * 1) * 2) * 3)
= 6

具体的な例ではリストの要素を逆転させる reverse という関数がある。これを仮想的なパターン (xs:x) を使って再帰関数で記述すると次のようになる。

reverse [] = []
reverse (xs:x) = x : reverse xs

これを foldl で実装するのだが、その前に一工夫する。foldl で reduce の際に渡される引き数の順序は f z x の順番になる。つまり、[..] : x だ。しかしこれではエラーになってしまうので、cons' z x = x : [..] となるように引き数の順番を逆転させておく。

let cons' = flip (:)

この cons' を使って reverse を foldl で実現したのが次の例だ。

Prelude> let cons' = flip (:)
Prelude> foldl cons' [] [1,2,3]
[3,2,1]

上のプログラムの展開の様子を機械に聞いてみた。

Prelude> foldl (\x y -> concat ["(","cons' ",x," ",y,")"]) "[]" ["1","2","3"]
"(cons' (cons' (cons' [] 1) 2) 3)"

中置記法の場合は次のようになる。

Prelude> foldl (\x y -> concat ["(",x," `cons'` ",y,")"]) "[]" ["1","2","3"]
"((([] `cons'` 1) `cons'` 2) `cons'` 3)"

このように左再帰型の再帰関数は foldl で簡単に書きなおすことができる。

高階関数の活用は RWH の著者たちが強調する Haskell の抽象性の実例のひとつだ。高階関数のおかげで Haskell では同じ型のループのような抽象的な概念をコードとして記述できる。このためコードが非常にコンパクトになり可読性の高いものになるのだ。
by tnomura9 | 2012-04-22 10:11 | Haskell | Comments(0)
<< RWH の読み方(38) 第4章 RWH の読み方(36) 第4章 >>