以下代码改编自一篇论文(RO Bjarnason,Stackless Scala With Free Monads)。
论文的标题指出了所提出的数据结构的总体目的——即在恒定堆栈空间中提供递归处理,并让用户以清晰的方式表达递归。
具体来说,我的目标是拥有一个单子结构,它可以在上升时基于恒定堆栈空间中的简单模式匹配对不可变的对树(二叉树)或列表(n-ary-tree)进行结构重写。
sealed trait Free[S[+_], +A]{
private case class FlatMap[S[+_], A, +B](
a: Free[S, A],
f: A => Free[S, B]
) extends Free[S, B]
def map[B](f: A => B): Free[S, B] = this.flatMap((a:A) => Done[S, B](f(a)))
def flatMap[B](f: A => Free[S, B]): Free[S, B] = this match {
case FlatMap(a, g) => FlatMap(a, (x: Any) => g(x).flatMap(f))
case x => FlatMap(x, f)
}
@tailrec
final def resume(implicit S: Functor[S]): Either[S[Free[S, A]], A] = {
this match {
case Done(a) => Right(a)
case More(k) => Left(k)
case FlatMap(a, f) => a match {
case Done(a) => f(a).resume
case More(k) => Left(S.map(k)((x)=>x.flatMap(f)))
case FlatMap(b, g) => b.flatMap((x: Any) => g(x).flatMap(f)).resume
}
}
}
}
case class Done[S[+_], +A](a: A) extends Free[S, A]
case class More[S[+_], +A](k: S[Free[S, A]]) extends Free[S,A]
trait Functor[F[+_]] {
def map[A, B](m: F[A])(f: A => B): F[B]
}
type RoseTree[+A] = Free[List, A]
implicit object listFunctor extends Functor[List] {
def map[A, B](a: List[A])(f: A => B) = a.map(f)
}
var tree : Free[List, Int]= More(List(More(List(More(List(Done(1), Done(2))), More(List(Done(3), Done(4))))), More(List(More(List(Done(5), Done(6))), More(List(Done(7), Done(8)))))))
使用 Free 是如何实现重写的?
模式匹配器的钩子在哪里?- 模式匹配器在上升时必须暴露给每个完整的子树!
这可以在 for 块内完成吗?
[问题已编辑。]