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

Question

我指定的特质对我的模型：

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

然后，我从记录从DB构建树：

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, _)) 
    } 
} 

此代码工作正常，但使用非尾递归调用。所以，我担心的是它会在大量记录中失败。我发现了一个非常好的article关于通过非尾递归使用Free monads Trampoline。 这看起来像要走的路，但我不能重写我的代码以使其堆栈安全。在本文的例子中，函数中只有一个递归调用，但在我的函数中可能会有很多，用于构建树。有人更有经验的自由monads可以帮助我吗？这甚至有可能吗？

Answer 1

在阐述我的意见，使build方法返回一个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。

直接进行尾递归仍然是一个很好的练习。

Answer 2

你可以重写你的函数作为尾递归，没有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) 
    }