使用遞歸函數堆棧 - 在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) 
    }