foldの融合則について #haskell

関数プログラミング 珠玉のアルゴリズムデザイン

さて、最近ハマっているこの本ですが、foldの融合則というのが出てきます。

日本語で検索しても、あまり情報が出てこないので、原著にあたって見たところ、原語では "the fusion law of foldr." と書いてありました。ちなみに、こちらで検索しても難しい感じのページが出るだけで、基本論文ばかりです。( ﾟдﾟ)

もはや、技術書というよりは、学術書の範囲ではないのかと。

ちなみに、foldl,foldr,foldrn,fold-mapなど、融合則にもレパートリーがあるようです。

foldrの融合定理

関数プログラミング入門 ―Haskellで学ぶ原理と技法―

同じ人が書いたこちらの本に、foldの融合について説明されていて、そこでfoldrとfoldlの融合定理についての解説もありました。

下記は、foldrの融合定理です。

f . foldr g a = foldr h b

以下の条件が揃うと、この等式が成立するらしいです。

• f が正格関数であること
• f a = b であること
• 任意のx,yに対し、f (g x y) = h x (f y) であること。

まず、fが「正格関数」とのことですが、どういう意味でしょうか？

下記のページにそれっぽい説明がありました。

本物のプログラマはHaskellを使う - 第8回 遅延評価の仕組み：ITpro

僕は、遅延評価じゃなくて即時評価される関数のことかな？と思ったのですが、違ったようです。

⊥(ボトム)という、エラーとか無限ループなどを司る値を与えられた時に、⊥に評価される関数のことを言うようです。

f ⊥ → ⊥

⊥には、評価されるとなんであっても即時に⊥になるという特徴があります。

そのため、引数を何らかの形で評価する関数「正格関数」ということになるようです。

つまり、「id」は、正格関数となり「const 1」は正格関数では無いです。

*Main> id undefined
*** Exception: Prelude.undefined

*Main> let ichi = const 1
*Main> ichi undefined
1

constは第２引数を評価しないので、undefinedでもエラーにならないです。

続いて、「f a = b」ですが、fの関数の型として。。。

f :: a -> b

こんな感じならば、問題ないということでしょうか。

定義上では、aもbも初期値を与えるものなので、左辺の初期値にfを適用したものと、右辺の初期値が等しければOKということになります。多分。(^^;

そして、最後の 「f (g x y) = h x (f y)」ですが、完全にパズルです。(^^;

説明が難しいので、一つ例を考えましたので紹介したいと思います。

定義: f . foldr g a = foldr h b
実例: (Just $ foldr (+) 0 $ [1,2,3]) == (foldr h (Just 0) $ [1,2,3])

これを満たす「h」を考えます。

まず、fが正格関数であることですが、「Just undefined」は、エラーになるので正格です。

つづいて、 f a = b ですが、定義と見比べるとa=0で、「(Just a) = (Just 0)」なので、合ってますね。

そして、f(g x y)ですが、Just ((+) 0 1)ですね。 h x (f y)は、h 1 (Just 0)が等しいということですので、hが下記のような関数になると成立するということですね。

h :: Int -> Maybe Int -> Maybe Int
h x (Just y) = Just $ x + y

なんかfmap的な感じもしなくもない。けど違うか？( ﾟдﾟ)?

まとめると

foldしてからfを適用するのと、fを適用しつつfoldするのが等価になるという定理です。

まだまだ「珠玉のアルゴリズムデザイン」の道は険しいですが、一歩ずつ登っている気がします。