使用 Scala 中的 Free Monads Trampoline 使递归函数堆栈安全吗？

Question

我已经为我的模型指定了特征：

sealed trait TreeStructureModel{
  val parentId: Option[Long]
  val title: String
  val id: Long
}

然后我根据数据库中的记录构建一棵树：

trait SimpleTree[+TreeStructureModel]{
  val title: String
  val id: Long
}
trait Node[+TreeStructureModel] extends SimpleTree[TreeStructureModel]{
  val inner: List[SimpleTree[TreeStructureModel]]
}
trait Leaf[+TreeStructureModel] extends SimpleTree[TreeStructureModel]

case class NodeImp[T <: TreeStructureModel](title: String, inner: List[SimpleTree[T]], id: Long) extends Node[T]
case class LeafImp[T <: TreeStructureModel](title: String, id: Long) extends Leaf[T]

object SimpleTree{
  def apply[T <: TreeStructureModel](ls: List[T]): List[SimpleTree[T]] = {
    def build(ls: List[T], current: T): SimpleTree[T] = {
      val children = ls.filter{ v => v.parentId.isDefined && v.parentId.get == current.id}
      if(children.isEmpty){
        LeafImp(title = current.title, id = current.id)
      } else {
        val newLs = ls.filterNot{ v => v.parentId.isDefined && v.parentId.get == current.id}
        NodeImp(title = current.title, id = current.id, inner = children.map{ch => build(newLs, ch)})
    }
  }
    val roots = ls.filter{ v => v.parentId.isEmpty}
    val others = ls.filterNot{ v => v.parentId.isEmpty}
    roots.map(build(others, _))
  }
}

这段代码工作正常，但使用了非尾递归调用。所以，我担心的是它会在大记录列表上失败。我发现了关于在非尾递归上使用 Free monads Trampoline 的精彩 article。这看起来像是一种方法，但我无法重写我的代码以使其堆栈安全。在本文的示例中，函数中只有一个递归调用，但在我的函数中可以有很多次，以构建一棵树。有没有对 Free monads 更有经验的人可以帮我解决这个问题？这可能吗？

Answer 1

您可以将您的函数重写为尾递归函数，而无需 scalaz。奥卡姆剃刀，你懂的...

 def build(
   ls: List[T], 
   kids: Map[Long, List[T]],
   result: Map[Long, SimpleTree[T]]
 ) = ls match {
   case Nil => result
   case head :: tail if result.contains(head.id) => build(tail, kids, result)
   case head :: tail =>          
     kids(head.id).partition(result.contains(_.id)) match {
       case (Nil, Nil) => 
         build(tail, kids, result + (head.id->LeafImp(head.title, head.id)))
       case (done, Nil) => 
         build(
           tail,
           kids, 
           result + 
           (head.id->NodeImp(head.title, head.id, done.map(_.id).map(result)))
         )
       case (_, missing) =>
         build(missing ++ tail, kids, result)
     }
  }

  def apply(ls: List[T]) = {
    val (roots, others) = list.partition(_.parentId.isEmpty)
    val nodes = build(ls, others.groupBy(_.parentId.get), Map.empty)
    roots.map(_.id).map(nodes)
  }

Answer 2

详细说明我的评论，使 build 方法 return 成为 Trampoline 并使用 traverse 代替 map:

import scalaz.Free.Trampoline
import scalaz.Trampoline
import scalaz.syntax.traverse._
import scalaz.std.list._

sealed trait TreeStructureModel{
  val parentId: Option[Long]
  val title: String
  val id: Long
}

trait SimpleTree[+TreeStructureModel]{
  val title: String
  val id: Long
}
trait Node[+TreeStructureModel] extends SimpleTree[TreeStructureModel]{
  val inner: List[SimpleTree[TreeStructureModel]]
}
trait Leaf[+TreeStructureModel] extends SimpleTree[TreeStructureModel]

case class NodeImp[T <: TreeStructureModel](title: String, inner: List[SimpleTree[T]], id: Long) extends Node[T]
case class LeafImp[T <: TreeStructureModel](title: String, id: Long) extends Leaf[T]

object SimpleTree{
  def apply[T <: TreeStructureModel](ls: List[T]): List[SimpleTree[T]] = {
    def build(ls: List[T], current: T): Trampoline[SimpleTree[T]] = {
      val children = ls.filter{ v => v.parentId.isDefined && v.parentId.get == current.id}
      if(children.isEmpty){
        Trampoline.done(LeafImp(title = current.title, id = current.id))
      } else {
        val newLs = ls.filterNot{ v => v.parentId.isDefined && v.parentId.get == current.id}
        children.traverse(build(newLs, _)).map(trees => NodeImp(title = current.title, id = current.id, inner = trees))
      }
    }
    val roots = ls.filter{ v => v.parentId.isEmpty}
    val others = ls.filterNot{ v => v.parentId.isEmpty}
    roots.map(build(others, _).run)
  }
}

请注意，为了使用 Trampoline，我对您的代码做了最少的必要更改。我进一步建议使用一次调用 partition 而不是一对 filter 和 filterNot.

直接使方法尾递归仍然是一个很好的练习。

使用 Scala 中的 Free Monads Trampoline 使递归函数堆栈安全吗？

Make recursive function stack - safe with Free Monads Trampoline in Scala?

recursion

scala

scalaz

scala-cats