[Haskell途中下車の旅] fold村散策（その２）
前回は foldl と foldr の概要を見ました。
今回はこの二つの高階関数の違いを見ていきましょう。
今回はこの二つの高階関数の違いを見ていきましょう。
Prelude に foldl で定義されたものが多い中で（前回の一覧参照） and と or は foldr で定義されていました。
(-) のように引数の順番を入れ替えると計算結果が違う場合はともかく
(&&) のように引数の順番を入れ替えても計算結果が変わらない場合は foldl と foldr のどちらを使ってもまったく同じようにも思えます。
ではなぜ and が foldr の方を使っているのか and [False,x2,x3,x4] の計算を例に見ていきましょう。 （False が入っているので論理積の結果が False になることは人間の目には明らかです）
and の定義は
(&&) の定義は
もし仮に foldl を使って
では (&&) の定義を変更して第２引数を先に具体化させるように
仮に x4 の値が False であれば (((True && False) && x2) && x3)) の計算にはまったく手を触れることなく結果として False を返せます。 確かにこのケースでも foldr のときと同じように一部分の計算を省ける可能性はありましたが リストの最後の要素（今の場合 x4）までたどっていかなければ計算に手をつけられない無駄は生じています。
前回「foldl はリストを左から順に処理していく『気分』、foldr はリストを左から順に処理していく『気分』」と書きましたがそれは「すべての引数を評価してから関数を実行する」という計算手順になれた脳が感じる『気分』であって実際の Haskell での計算手順はその『気分』どおりに進むとは限らないのです。
上記の例は有限リストが対象でしたので計算量に違いがあっても foldl と foldr の両方とも最終結果にたどりつくことができました。しかし無限リストの場合は foldl と foldr の違いが顕著にでます。無限リスト [x1,x2,x3,...] に対する foldl の計算の
実際に取りだせるかどうかは f がどういう関数かによります。 f が (+) のときはうまくいきませんが (&&) のときは上でも見たように無限の計算をしなくても False という結果を返せることがあります。
またリストのコンストラクタである (:) と foldr の組み合わせも相性がよく、map と filter（両関数とも無限リストに対応できる）も (:) を使って
一方 (:) と foldl を使って書ける reverse
次回は fold の親戚達（scan系、mapAccum系）の紹介と高階関数の効能について説明します。
ではなぜ and が foldr の方を使っているのか and [False,x2,x3,x4] の計算を例に見ていきましょう。 （False が入っているので論理積の結果が False になることは人間の目には明らかです）
and の定義は
and = foldr (&&) Trueでしたので and [False,x2,x3,x4] の値は
False && (x4 && (x2 && (x3 && True)))と表せます。Haskell は外側から具体的な値が必要になる順に計算していきます。
(&&) の定義は
True && x = x False && _ = Falseでしたから False && _ = False の方の処理が適用され (x4 && (x2 && (x3 && True))) の計算にはまったく手を触れることなく結果として False を返すことができます。
もし仮に foldl を使って
and = foldl (&&) Trueとして計算したらどうなるでしょう。foldl (&&) True [False,x2,x3,x4] の値は
((((True && False) && x2) && x3) && x4ですから x4 の左の (&&) は第１引数が True か False かはっきりさせるため、まず
((True && False) && x2) && x3を計算しに行きます。同様にして
(True && False) && x2の値を調べに行き、さらに
True && Falseにたどり着いたところでやっと値が具体的になったので来た道を戻りながら値を計算していくことになります。
では (&&) の定義を変更して第２引数を先に具体化させるように
x && True = x _ && False = Falseとしたら上の計算はどうなるでしょう。まず
(((True && False) && x2) && x3) && x4の x4 の方の値を先に True か False はっきりさせにいきます。
仮に x4 の値が False であれば (((True && False) && x2) && x3)) の計算にはまったく手を触れることなく結果として False を返せます。 確かにこのケースでも foldr のときと同じように一部分の計算を省ける可能性はありましたが リストの最後の要素（今の場合 x4）までたどっていかなければ計算に手をつけられない無駄は生じています。
前回「foldl はリストを左から順に処理していく『気分』、foldr はリストを左から順に処理していく『気分』」と書きましたがそれは「すべての引数を評価してから関数を実行する」という計算手順になれた脳が感じる『気分』であって実際の Haskell での計算手順はその『気分』どおりに進むとは限らないのです。
上記の例は有限リストが対象でしたので計算量に違いがあっても foldl と foldr の両方とも最終結果にたどりつくことができました。しかし無限リストの場合は foldl と foldr の違いが顕著にでます。無限リスト [x1,x2,x3,...] に対する foldl の計算の
... (f (f (f z x1) x2) x3) ...では無限に続く外側の括弧に阻まれて内側の有限の計算部分にまったく手がとどきません。一方 foldr の
f x1 (f x2 (f x3 (... ...)))では f, x1 などが外側に近いほうにあるので計算結果の一部または全部が取り出せる可能性がでてきます。
実際に取りだせるかどうかは f がどういう関数かによります。 f が (+) のときはうまくいきませんが (&&) のときは上でも見たように無限の計算をしなくても False という結果を返せることがあります。
またリストのコンストラクタである (:) と foldr の組み合わせも相性がよく、map と filter（両関数とも無限リストに対応できる）も (:) を使って
map f xs = foldr (\a b -> f a: b) [] xs filter p xs = foldr (\a b -> if p a then a:b else b) [] xsと書くことができます。
一方 (:) と foldl を使って書ける reverse
reverse xs = foldl (\b a -> a:b) [] xsは無限リストに対応できません。
次回は fold の親戚達（scan系、mapAccum系）の紹介と高階関数の効能について説明します。
