セカイノカタチスマートフォン用の表示で見るセカイノカタチ世界のカタチを探求するブログ。関数型言語に興味があり、HaskellやScalaを勉強中。先日、foldの融合則についての記事を書きました。セカイノカタチこちらHaskellで書いたのですが、Scalaに書き直してみました。見るこちらの本に、foldの融合について説明されています。下記は、foldrの融合定理です。bこれだとHaskellなので、Scalaっぽい感じで書くと。tra.foldRight[Option[Int]](Some(0))(h)}こんな感じでしょうか?foldRightがTraversable[A]のメソッドだったので、traと書いてみましたが、コレクションならだいたいなんでも取れるってことです。この等式が以下の条件で成立するらしいです。fが「正格関数」とのことですが、どういう意味でしょうか?下記のページにそれっぽい説明がありました。遅延評価の仕組み:ITpro僕は、遅延評価じゃなくて即時評価される関数のことかな?と思ったのですが、違ったようです。⊥(ボトム)という、エラーとか無限ループなど、純粋な関数や数値の枠外に飛び出てしまった事を表す値があるのですが、実行時に引数が⊥だった場合、関数自体が⊥に評価される関数のことを言うようです。⊥には、評価されるとなんであっても即時に⊥になるという特徴があります。そのため、引数を何らかの形で評価する関数「正格関数」ということになるようです。「id」は、正格関数となり「const(1)」は正格関数では無いです。1constは第2引数を評価しないので、???でもエラーにならないです。b」ですが、fの関数の型として。???こんな感じならば、問題ないということでしょうか。定義上では、aもbも初期値を与えるものなので、左辺の初期値にfを適用したものと、右辺の初期値が等しければOKということになります。h(x,f(y))」ですが、完全にパズルです。(^^;説明が難しいので、一つ例を考えましたので紹介したいと思います。list.foldRight[Option[Int]](Some(0))(h)みんな大好きOption[A]を使いました。(^^)vこれを満たす「h」を考えます。fが正格関数であることですが、「Some(???)」は、エラーになるので正格です。定義と見比べるとaの部分には(0)と書いてあり、bの部分には(Some(0))とあります。Some(0)」なので、合ってますね。h(x,f(y))は、h(1,Some(0))が等しいということですので、条件に合うような関数を考えます。hが下記のような関数になると成立するということですね。}}まとめるとfoldしてからfを適用するのと、fを適用しつつfoldするのが等価になるという定理です。前者より後者の方が効率が良くなるため、条件が成立するようなhを探すために利用するようです。「珠玉のアルゴリズムデザイン」の道は険しいですが、一歩ずつ登っている気がします。*1:動きません(^^;。はてなブログProシステム開発の世界で15年の山の民による、世界のカタチを探求するブログ。(4)はてなブログをはじめよう!qtamakiさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。