2

Scala 2.13的迁移指南解释说，它Traversable已被删除，Iterable应该改用它。对于一个使用访问者在树的类中实现foreach方法的项目来说，这种变化特别烦人：Node

case class Node(val subnodes: Seq[Node]) extends Traversable[Node] {
  override def foreach[A](f: Node => A) = Visitor.visit(this, f)
}

object Visitor {
  def visit[A](n: Node, f: Node => A): Unit = {
    f(n)
    for (sub <- n.subnodes) {
      visit(sub, f)
    }
  }
}

object Main extends App {
  val a = Node(Seq())
  val b = Node(Seq())
  val c = Node(Seq(a, b))
  for (Node(subnodes) <- c) {
    Console.println("Visiting a node with " + subnodes.length + " subnodes")
  }
}

输出：

Visiting a node with 2 subnodes
Visiting a node with 0 subnodes
Visiting a node with 0 subnodes

迁移到 Scala 2.13 的一个简单修复方法是首先将访问过的元素存储在remaining缓冲区中，然后使用该缓冲区返回一个迭代器：

import scala.collection.mutable
import scala.language.reflectiveCalls

case class Node(val subnodes: Seq[Node]) extends Iterable[Node] {
  override def iterator: Iterator[Node] = {
    val remaining = mutable.Queue.empty[Node]
    Visitor.visit(this, item => iterator.remaining.enqueue(item))
    remaining.iterator
  }
}

// Same Visitor object
// Same Main object

这种解决方案的缺点是它引入了对 GC 施加压力的新分配，因为访问的元素的数量通常非常大。

您对如何从 迁移Traversable到Iterable使用现有访问者但不引入新分配有什么建议吗？

4

3 回答 3

3

正如您所注意到的，您需要扩展Iterable而不是Traversable. 你可以这样做：

case class Node(name: String, subnodes: Seq[Node]) extends Iterable[Node] {
  override def iterator: Iterator[Node] = Iterator(this) ++ subnodes.flatMap(_.iterator)
}

val a = Node("a", Seq())
val b = Node("b", Seq())
val c = Node("c", Seq(a, b))
val d = Node("d", Seq(c))

for (node@Node(name, _) <- d) {
  Console.println("Visiting node " + name + " with " + node.subnodes.length + " subnodes")
}

输出：

Visiting node d with 1 subnodes
Visiting node c with 2 subnodes
Visiting node a with 0 subnodes
Visiting node b with 0 subnodes

然后您可以进行更多操作，例如：

d.count(_.subnodes.length > 1)

代码在Scastie运行。

于 2021-01-20T13:57:21.713 回答
2

我们最终编写了一个最小的Traversable特征，只实现了我们代码库中使用的方法。这样就没有额外的开销，也不需要更改访问者的逻辑。

import scala.collection.mutable

/** A trait for traversable collections. */
trait Traversable[+A] {
  self =>

  /** Applies a function to all element of the collection. */
  def foreach[B](f: A => B): Unit

  /** Creates a filter of this traversable collection. */
  def withFilter(p: A => Boolean): Traversable[A] = new WithFilter(p)

  class WithFilter(p: A => Boolean) extends Traversable[A] {
    /** Applies a function to all filtered elements of the outer collection. */
    def foreach[U](f: A => U): Unit = {
      for (x <- self) {
        if (p(x)) f(x)
      }
    }

    /** Further refines the filter of this collection. */
    override def withFilter(q: A => Boolean): WithFilter = {
      new WithFilter(x => p(x) && q(x))
    }
  }

  /** Finds the first element of this collection for which the given partial
    * function is defined, and applies the partial function to it.
    */
  def collectFirst[B](pf: PartialFunction[A, B]): Option[B] = {
    for (x <- self) {
      if (pf.isDefinedAt(x)) {
        return Some(pf(x))
      }
    }
    None
  }

  /** Builds a new collection by applying a partial function to all elements
    * of this collection on which the function is defined.
    */
  def collect[B](pf: PartialFunction[A, B]): Iterable[B] = {
    val elements = mutable.Queue.empty[B]
    for (x <- self) {
      if (pf.isDefinedAt(x)) {
        elements.append(pf(x))
      }
    }
    elements
  }
}
于 2021-02-04T08:08:54.223 回答
2

这是一个可以实现您的代码LazyList并且不需要访问者的示例：

case class Node(val subnodes: Seq[Node]) {
  
  def recursiveMap[A](f: Node => A): LazyList[A] = {
    def expand(node: Node): LazyList[Node] = node #:: LazyList.from(node.subnodes).flatMap(expand)
    expand(this).map(f)
  }
}

val a = Node(Seq())
val b = Node(Seq())
val c = Node(Seq(a, b))

val lazyList = c.recursiveMap { node =>
  println("computing value")
  "Visiting a node with " + node.subnodes.length + " subnodes"
}

println("started computing values")

lazyList.iterator.foreach(println)

输出

started computing values
computing value
Visiting a node with 2 subnodes
computing value
Visiting a node with 0 subnodes
computing value
Visiting a node with 0 subnodes

如果您lazyList自己不存储引用而只存储迭代器，那么 JVM 将能够随时 GC 值。

于 2021-01-20T14:12:15.393 回答