Trampoline

トランポリンをご存知でしょうか。
相互再帰を最適化するものです。
私はプログラミングClojureを読んではじめて知りました。

相互再帰を最適化すると言っても、既存のものを最適化することは出来ません。
最適化のためには関数をトランポリンを使ったものにしなくてはなりません。

さて、そのトランポリンですが、実はScalazには用意されているのです！

多分6.0.4から入った・・・と思う。
私がStack Overflowで質問したからですね！フフン！

まぁ、たぶん質問しなくても入ってたと思いますが・・・・

なぜTrampolineが入ったのか

以下推測

それは、IOモナドの最適化のためだと思われます。

以前のIOモナドは、>>=で連結していくと評価時にIOの呼び出しが深くなってしまい、StackOverflowErrorを起こしていました。

そこで、トランポリンを導入することで最適化がされました。

命名規則をみると、Scalaz7から輸入されたようです。

なので、IOが問題になっていなかったら、Scalaz6では入っていなかったかも・・・？

使い方

プログラミングClojureの例を参考に偶数、奇数を調べる関数を書いてみる。

まずはトランポリンを使わずに

	lazy val odd: Int => Boolean = {
	case 0 => false
	case n => even(n - 1)
	}
	lazy val even: Int => Boolean = {
	case 0 => true
	case n => odd(n - 1)
	}

view raw trampoline1.scala hosted with ❤ by GitHub

どれくらいでスタックがあふれるか調べる。

	assert(odd(1))
	assert(odd(11))
	assert(odd(111))
	assert(odd(1111))
	assert(odd(11111))
	// assert(odd(111111)) StackOverflow

view raw trampoline2.scala hosted with ❤ by GitHub

6桁で落ちるとは・・・・

トランポリン版

	lazy val odd: Int => Free.Trampoline[Boolean] = {
	case 0 => Free.return_(false)
	case n => Free.suspend(even(n - 1))
	}
	lazy val even: Int => Free.Trampoline[Boolean] = {
	case 0 => Free.return_(true)
	case n => Free.suspend(odd(n-1))
	}

view raw trampoline3.scala hosted with ❤ by GitHub

実行するにはrunメソッドを呼びます。

	assert(odd(11111).run)
	assert(odd(111111).run)
	assert(odd(1111111).run)
	assert(odd(11111111).run)
	assert(odd(111111111).run)

view raw trampoline4.scala hosted with ❤ by GitHub

これは全く落ちない。
あと多分速い。

※追記
遅かった・・・・

結論

プログラミングClojureにあるとおり、なるべく最適なアルゴリズム、自己再帰で書きましょう。
IOモナドのような特殊なケースはあまりないと思います。

さて、このTrampoline、じつはtype aliasです。
type Trampoline [+A] = Free[Function0, A]
と定義されており、Freeがもっと一般化されたなにかであることがわかります。

Freeについてはいつか調べるor誰か調べてくれる・・・はず・・・・・