scala - Stackless Scala 和 Free Monads，完整示例

Question

以下代码改编自一篇论文(R. O. Bjarnason，Stackless Scala With Free Monads)。

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

具体来说，我的目标是拥有一个单子(monad)结构，它可以在上升时基于恒定堆栈空间中的简单模式匹配对不可变的对树(二叉树)或列表(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 是如何实现重写的？

模式匹配器的钩子(Hook)在哪里？ - 模式匹配器在上升时必须暴露给每个完整的子树!

这可以在 for block 内完成吗？

[问题已编辑。]

Answer 1

更新:下面的答案地址 an earlier version的问题，但大多仍然是相关的。

首先，您的代码不会按原样工作。您可以使所有内容保持不变，或者使用原始论文中的方差注释。为简单起见，我将采用不变的路线(完整示例请参见 here)，但我也刚刚确认本文中的版本适用于 2.10.2。

首先回答您的第一个问题:您的二叉树类型与 BinTree[Int] 同构.不过，在我们展示这一点之前，我们需要一个用于 pair 类型的仿函数:

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 的 monad通过用包含其前任和后继的树替换每个叶子值:

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)))
    )),
    ...

依此类推，正如预期的那样。

对于你的第二个问题:如果你想为一棵玫瑰树做同样的事情，你只需用一个列表(或一个流)替换这对。你需要为列表提供一个仿函数实例，就像我们在上面对对所做的那样，然后你就得到了一个带有 Done(x) 的树。代表树叶和 More(xs)为分支机构。

您的类型需要 map对于 for - 理解语法工作。幸运的是你可以写 map根据 flatMap和 Done — 只需将以下内容添加到 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, _] 也同样适用。玫瑰树。