foldの融合則についてScala版 #scalajp

先日、foldの融合則についての記事を書きました。

こちらHaskellで書いたのですが、Scalaに書き直してみました。

foldrの融合定理

こちらの本に、foldの融合について説明されています。

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

f . foldr g a = foldr h b

これだとHaskellなので、Scalaっぽい感じで書くと。。

def sample(tra: Traversable[Int]) {
  Some(tra.foldRight(0)(_+_)) == tra.foldRight[Option[Int]](Some(0))(h)
}

こんな感じでしょうか？

foldRightがTraversable[A]のメソッドだったので、traと書いてみましたが、コレクションならだいたいなんでも取れるってことです。

そして、この等式が以下の条件で成立するらしいです。

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

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

<a href="http://itpro.nikkeibp.co.jp/article/COLUMN/20070305/263828/">第8回　遅延評価の仕組み</a>

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

⊥(ボトム)という、エラーとか無限ループなど、純粋な関数や数値の枠外に飛び出てしまった事を表す値があるのですが、実行時に引数が⊥だった場合、関数自体が⊥に評価される関数のことを言うようです。

f(⊥) → ⊥

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

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

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

def id[A](a: =>A): A = a
id(???)
=> scala.NotImplementedError
def const1[A](a: => A):Int = 1
const(???)
=> 1

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

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

f[A,B](a:A):B = ???

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

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

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

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

定義: f(traversable.foldRight(a)(g)) == traversable.foldRight(b)(h)
実例: Some(list.foldRight(0)(_+_)) == list.foldRight[Option[Int]](Some(0))(h)

みんな大好きOption[A]を使いました。(^^)v

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

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

つづいて、 f(a) == b ですが、定義と見比べるとaの部分には(0)と書いてあり、bの部分には(Some(0))とあります。つまり「Some(a) = Some(0)」なので、合ってますね。

そして、f(g(x,y))ですが、x=1,y=0としたとき、Some( (_+_)(1,0) )*1ですね。 h(x,f(y))は、h(1,Some(0))が等しいということですので、条件に合うような関数を考えます。

hが下記のような関数になると成立するということですね。

def h(a: Int, b: Option[Int]): Option[Int] = {
  b match {
    case Some(x) => Some(a+x)
    case None => None
  }
}

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

前者より後者の方が効率が良くなるため、条件が成立するようなhを探すために利用するようです。

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

*1:動きません(^^;。実際はSome( ( (x:Int,y:Int)=>x+y)(1,0) )と書く必要があります