Stackless Scala免费Monads，完整示例

Question

下面的代码是从一篇论文（R. O. Bjarnason，Stackless Scala with Free Monads）改编而来的。

该论文的标题指向了所提出的数据结构的目的 - 即在固定堆栈空间中提供递归处理，并让用户以清晰的方式表达递归。

具体而言，我的目标是建立一个monadic结构，在升序时基于简单模式匹配在恒定堆栈空间中提供对不变树对（二叉树）或列表（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实现重写？

模式匹配器的钩子在哪里？ - 上升时，模式匹配器必须暴露给每个整个子树！

这可以在一个块内完成吗？ [此问题已编辑]

Answer 1

更新：下面的地址问题的an earlier version答案，但大多仍然具有现实意义。

---

首先，您的代码不会按原样运行。您可以使所有内容保持不变，也可以使用原始纸张中的差异注释。为了简单起见，我将采取不变的路线（参见here作为一个完整的例子），但是我也刚刚确认了论文中的版本将在2.10.2中工作。

要首先回答你的第一个问题：你的二叉树类型同构于BinTree[Int]。之前，我们可以证明这一点，但是，我们需要一个仿函数我们对类型：

implicit object pairFunctor extends Functor[Pair] { 
    def map[A, B](a: Pair[A])(f: A => B) = (f(a._1), f(a._2)) 
} 

现在我们可以使用resume，我们将需要从BinTree回T转换：

def from(tree: T): BinTree[Int] = tree match { 
    case L(i) => Done(i) 
    case F((l, r)) => More[Pair, Int]((from(l), from(r))) 
} 

def to(tree: BinTree[Int]): T = tree.resume match { 
    case Left((l, r)) => F((to(l), to(r))) 
    case Right(i) => L(i) 
} 

现在，我们可以定义你的榜样树：

var z = 0 
def f(i: Int): T = if (i > 0) F((f(i - 1), f(i - 1))) else { z = z + 1; L(z) } 
val tree = f(3) 

让我们证明我们同构和BinTree单子用含其前身和后继树替换每个叶子值：

val newTree = to(
    from(tree).flatMap(i => More[Pair, Int]((Done(i - 1), Done(i + 1)))) 
) 

一些格式化之后，结果会是这样的：

F((
    F((
    F((
     F((L(0), L(2))), 
     F((L(1), L(3))) 
    )), 
    F((
     F((L(2), L(4))), 
     F((L(3), L(5))) 
    )), 
    ... 

等等，符合市场预期。

对于第二个问题：如果你想为玫瑰树做同样的事情，你只需要用一个列表（或一个流）替换这个对。您需要为列表提供一个函子实例，就像我们在上面为pair进行的操作一样，然后您得到了一棵代表树叶的Done(x)树和分支的More(xs)树。

---

你的类型需要map为for -comprehension语法工作。幸运的是，你可以在flatMap和Done条款写map - 只是添加以下的Free定义：

def map[B](f: A => B): Free[S, B] = this.flatMap(f andThen Done.apply) 

现在以下是完全一样的newTree以上：

val newTree = to(
    for { 
    i <- from(tree) 
    m <- More[Pair, Int]((Done(i - 1), Done(i + 1))) 
    } yield m 
) 

同事情将与Free[List, _]玫瑰树一起工作。