时间戳

首页 > 解决方案 > 试图理解 Scala 中树上的 scanLeft

scala - 试图理解 Scala 中树上的 scanLeft

问题描述

我在 Coursera 的课程中​​，我试图理解树上 scanLeft 的逻辑。我们有以下代码：

这里我们有一个输入树（没有中间值，只有叶子中的值）并返回一个具有中间值的树（节点中有值）

 def upsweep[A](t: Tree[A], f: (A,A) => A): TreeRes[A] = t match {
      case Leaf(v) => LeafRes(v)
      case Node(l, r) => {
           val (tL, tR) = parallel(upsweep(l, f), upsweep(r, f))
           NodeRes(tL, f(tL.res, tR.res), tR)
      }
 }

下面的代码给出了一个具有中间值的树（在节点中有值）返回一个没有中间值的树（a0 是树 t 左侧所有元素的归约）。

 def downsweep[A](t: TreeRes[A], a0: A, f : (A,A) => A): Tree[A] = t match {
      case LeafRes(a) => Leaf(f(a0, a))
      case NodeRes(l, _, r) => {
           val (tL, tR) = parallel(downsweep[A](l, a0, f),
           downsweep[A](r, f(a0, l.res), f))
      Node(tL, tR) } 
 }

最后是scanLeft代码：

 def scanLeft[A](t: Tree[A], a0: A, f: (A,A) => A): Tree[A] = {
      val tRes = upsweep(t, f)
      val scan1 = downsweep(tRes, a0, f)
      prepend(a0, scan1)
 }

我的问题是，为什么必须在下扫之前使用上扫方法？通过上扫我们生成中间值，然后通过下扫我们“删除”（我们不需要使用）它们。

提前致谢。

标签： scala

解决方案

实际上更仔细地看这部分

case NodeRes(l, _, r) => {
       val (tL, tR) = parallel(downsweep[A](l, a0, f),
       downsweep[A](r, f(a0, l.res), f))

什么是l.res？为什么需要它？（它是在 upsweep 中创建的）我建议你一步一步地在一张纸上画出这个算法到底做了什么，这个算法具有简单的功能，如 (_ + _)。此外，如果您不了解这样做，这也是非常好的技术，只需一步一步轻松并自己解决。

推荐阅读