Scalaz Tree - 从 TreeLoc 集合中找到 min/max 深度

Question

在 Scalaz 中我有一个 Tree[A] 喜欢；

'A'.node('B'.leaf, 'C'.node('D'.leaf), 'E'.leaf)

现在假设我有一个通过树递归的函数 returns TreeLoc;

def getCharLoc(c: Char) = tree.loc.find(_.getLabel == c)

然后我做类似

的事情

Seq('D','E').flatMap(getCharLoc)

如何找到树中最低的 and/or 最高的 loc。在上面的示例中，'D' 是 lowest/deepest 位置，'E' 是 highest/shallowest 位置。

我在想每个 loc 都有一个 .path 方法，其中 returns 一个 Stream 从 loc 到根。在此调用 .length 将给出深度计数，可以在左侧折叠中进行比较，但感觉很笨重。

我怎样才能做到这一点？

Answer 1

我可以用尾递归函数计算 parents，不确定你是否会考虑更多或更少 "clunky":

val tree = 'A'.node('B'.leaf, 'C'.node('D'.leaf), 'E'.leaf)

@tailrec def countParents(loc: Option[TreeLoc[Char]], acc: Int = 0): Int = 
  loc >>= { _.parent } match {
    case None => acc
    case next @ _ => countParents(next, acc + 1)
  }

println(countParents(tree.loc.find(_.getLabel == 'D'))) // 2
println(countParents(tree.loc.find(_.getLabel == 'E'))) // 1

Scalaz Tree - 从 TreeLoc 集合中找到 min/max 深度

Scalaz Tree - finding the min/max depth from a TreeLoc set

scala

tree

stream

scalaz