読者です 読者をやめる 読者になる 読者になる

セカイノカタチ

世界のカタチを探求するブログ。関数型言語に興味があり、HaskellやScalaを勉強中。最近はカメラの話題も多め

マーブルワーズ

foldの融合則について #haskell

Haskell アルゴリズム プログラミング 技術書 関数型

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

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

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

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

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

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

foldrの融合定理

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

関数プログラミング入門 ―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は第2引数を評価しないので、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するのが等価になるという定理です。

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