中断可能な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

全然脱線なんだけど

List(1, 2, 6, 3, 4, 5).limitFoldLeft(0) { 
   case (a, b) => if (b > 5) End(a) else Continue(a+b)
}

こう書いた方がいいか

List(1, 2, 6, 3, 4, 5).limitFoldLeft(0) { 
   case (a, b) if b > 5 => End(a)
   case (a, b) => Continue(a+b)
}

こう書いた方がいいか地味に迷う。

確かにmatch式の中で分岐するのはもにょりますね。

そうなんですよ。もにょもにょ

保守性考えるとこっちですね。

List(1, 2, 6, 3, 4, 5).limitFoldLeft(0) { 
   case (a, b) if b > 5 => End(a)
   case (a, b) => Continue(a+b)
}

条件が簡単に追加できますし。

List(1, 2, 6, 3, 4, 5).limitFoldLeft(0) { 
   case (a, b) if a > 10 => End(a)
   case (a, b) if b > 5 => End(a)
   case (a, b) => Continue(a+b)
}

なるほど。
ガード節だけ異なる場合はまとめた方が保守性考えると良さそうな気がします。

List(1, 2, 6, 3, 4, 5).limitFoldLeft(0) {
   case (a, b) if a > 10 || b > 5 => End(a)
   case (a, b) => Continue(a+b)
}

パターンが異なるならパターン分けた方が良さそうですね。

List(1, 2, 6, 3, 4, 5).limitFoldLeft(0) { 
   case (a, _) if a > 10 => End(a)
   case (a, b) if b > 5 => End(a)
   case (a, b) => Continue(a+b)
}

"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
というか僕の継続モナドの理解も怪しい気がしてきました＞＜
このコードじっくり読んで勉強させてもらいます！ありがとうございます！！