中断可能なfold

1.scala

sealed trait FoldResult[+A]
case class Continue[+A](a: A) extends FoldResult[A]
case class End[+A](a: A) extends FoldResult[A]

class LimitFoldable[+A](underlying: Traversable[A]) {
  def limitFoldLeft[B](init: B)(f: (B, A) => FoldResult[B]): B = {
    @tailrec
    def fold(sentinel: B, rest: Traversable[A]): B = {
      if (rest.isEmpty) return sentinel
      f(sentinel, rest.head) match {
        case End(e) => e
        case Continue(e) => fold(e, rest.tail)
      }
    }
    fold(init, underlying)
  }
}
implicit def traversableToLimitFoldable[A](underlying: Traversable[A]) =
  new LimitFoldable(underlying)

2.scala

scala> List(1, 2, 3, 4, 5, 6, 7).limitFoldLeft(0) {
     |   case (a, b) => if (a > 10) End(a) else Continue(a+b)
     | }
res0: Int = 15

scala> List(1, 2, 3, 4, 5, 6, 7).limitFoldLeft(0) {
     |   case (a, b) => if (a > 1000) End(a) else Continue(a+b)
     | }
res1: Int = 28

"org.scalaz" % "scalaz-core_2.9.1" % "6.0.4"

scala> import scalaz._,Scalaz._
import scalaz._
import Scalaz._

scala> import Trampoline._
import Trampoline._

scala> List(1,2,6,3,4,5).foldLeftM(0){ (a, b) => (a > 5) ? (Free.pause >| a) | Free.return_(a + b)}
res0: scalaz.Free.Trampoline[Int] = Gosub(Suspend(<function0>),<function1>)

scala> res0.run
res1: Int = 9

scalaz6.0.4だと、Trampoline の monad の instance はデフォルトでは import されない らしくて、import Trampoline._ を加えたら、Trampoline でできた(？)

おお、scalaz6 だとデフォルト import されてないんですね。

scala> List(1,2,6,3,4,5).foldLeftM(0){ (a, b) => (a > 5) ? (Free.pause >| a) | Free.return_(a + b)}
res0: scalaz.Free.Trampoline[Int] = Gosub(Suspend(<function0>),<function1>)

scala> res0.run
res1: Int = 9

scala> List(1,2,6,3,4,5).foldLeftM(0){ (a, b) => (b > 5) ? (Free.pause >| a) | Free.return_(a + b)}
res2: scalaz.Free.Trampoline[Int] = Gosub(Suspend(<function0>),<function1>)

scala> res2.run
res3: Int = 15

やっぱり中断ではなくて条件に合致する場合skipされてる感じですね。

Continuationモナドを使うと良いと思うのですが、
cf: http://www.sampou.org/haskell/a-a-monads/html/contmonad.html

case class Cont[R, +A](runCont: (A => R) => R) {
  def flatMap[B](f: A => Cont[R, B]): Cont[R, B] = {
    Cont(k => this.runCont(a => f(a).runCont(k)))
  }
}
object Cont {
  def return_[R, A](a: A) = Cont[R, A](k => k(a))
  def callcc[R, A, B](f: (A => Cont[R, B]) => Cont[R, A]) =
    Cont[R, A](k => f(a => Cont(x => k(a))).runCont(k))
}

class LimitFoldable[+A](underlying: Traversable[A]) {
  def limitFoldLeft[B](init: B)(f: (B, A, B => Cont[B, B], B => Cont[B, B]) => Cont[B, B]): B = {
    def return_(b: B) = Cont.return_[B, B](b)
    def continue_(b: B) = return_(b)

    Cont.callcc[B, B, B](break_ =>  {
      underlying.foldLeft(return_(init))((cont: Cont[B, B], a: A) => {
        cont flatMap (b => f(b, a, continue_, break_))
      })
    }).runCont(b => b)
  }
}
implicit def traversableToLimitFoldable[A](underlying: Traversable[A]) =
  new LimitFoldable(underlying)

scala> List(1, 2, 3, 4, 5, 6, 7).limitFoldLeft(0)((b, a, continue_, break_) =>  
     |   if (a > 5) break_(b) else continue_(a + b)
     | )
res1: Int = 15

scala> List(1, 2, 3, 6, 4, 5, 6, 7).limitFoldLeft(0)((b, a, continue_, break_) =>  
     |   if (a > 5) break_(b) else continue_(a + b)
     | )
res2: Int = 6

このままだとスタックオーバーフローするのでTrampolineしたいのですが、
噂によるとContinuationモナドはFreeで書けるらしいので、最初からFreeで書けばすべて解決しそうな気も。
Freeを理解しようとしたが圏力が及ばなかった……

なるほど継続モナド！まさしくこの用途にぴったりですね。
ってことは限定継続つかえばスタックオーバーフローの問題も解決できるんですかね？

ContinuationモナドとFreeモナドの関係は僕もぜんぜん理解できてませんorz
というか僕の継続モナドの理解も怪しい気がしてきました＞＜
このコードじっくり読んで勉強させてもらいます！ありがとうございます！！