scala - 如何使在 Scala 中实现的树对高阶集合函数有用？

Question

我在 Scala 中实现了一个简单的树结构，如下所示:

sealed abstract class FactsQueryAst[FactType] {
}

object FactsQueryAst {
  case class AndNode[FactType](subqueries: Seq[FactsQueryAst[FactType]]) extends FactsQueryAst[FactType]
  case class OrNode[FactType](subqueries: Seq[FactsQueryAst[FactType]]) extends FactsQueryAst[FactType]
  case class Condition[FactType](fact: FactType, value: FactValue) extends FactsQueryAst[FactType]
}

是否有任何相对简单的方法可以使这个结构与 map、foldLeft 或 filter 等高阶函数一起工作？有一篇关于为您自己的集合实现 Traversable 特征的好文章( http://daily-scala.blogspot.com/2010/04/creating-custom-traversable.html )，但对于树案例来说似乎过于复杂，或者至少我缺少一些原则。

UPD。我尝试如下实现天真的 Traversable，但它会导致仅用于打印值的无限循环。

sealed abstract class FactsQueryAst[FactType] extends Traversable[FactsQueryAst.Condition[FactType]]

object FactsQueryAst {
  case class AndNode[FactType](subqueries: Seq[FactsQueryAst[FactType]]) extends FactsQueryAst[FactType] {
    def foreach[U](f: (Condition[FactType]) => U) {subqueries foreach {_.foreach(f)}}
  }
  case class OrNode[FactType](subqueries: Seq[FactsQueryAst[FactType]]) extends FactsQueryAst[FactType] {
    def foreach[U](f: (Condition[FactType]) => U) {subqueries foreach {_.foreach(f)}}
  }
  case class Condition[FactType](fact: FactType, value: FactValue) extends FactsQueryAst[FactType]{
    def foreach[U](f: (Condition[FactType]) => U) {f(this)}
  }
}

无限循环的堆栈跟踪如下所示:

at tellmemore.queries.FactsQueryAst$Condition.stringPrefix(FactsQueryAst.scala:65532)
at scala.collection.TraversableLike$class.toString(TraversableLike.scala:639)
at tellmemore.queries.FactsQueryAst.toString(FactsQueryAst.scala:5)
at java.lang.String.valueOf(String.java:2854)
at scala.collection.mutable.StringBuilder.append(StringBuilder.scala:197)
at scala.collection.TraversableOnce$$anonfun$addString$1.apply(TraversableOnce.scala:322)
at tellmemore.queries.FactsQueryAst$Condition.foreach(FactsQueryAst.scala:23)
at scala.collection.TraversableOnce$class.addString(TraversableOnce.scala:320)
at tellmemore.queries.FactsQueryAst.addString(FactsQueryAst.scala:5)
at scala.collection.TraversableOnce$class.mkString(TraversableOnce.scala:286)
at tellmemore.queries.FactsQueryAst.mkString(FactsQueryAst.scala:5)
at scala.collection.TraversableLike$class.toString(TraversableLike.scala:639)
at tellmemore.queries.FactsQueryAst.toString(FactsQueryAst.scala:5)
at java.lang.String.valueOf(String.java:2854)
at scala.collection.mutable.StringBuilder.append(StringBuilder.scala:197)
at scala.collection.TraversableOnce$$anonfun$addString$1.apply(TraversableOnce.scala:322)
at tellmemore.queries.FactsQueryAst$Condition.foreach(FactsQueryAst.scala:23)

Answer 1

让我们将 FactType 重命名为看起来更像类型参数的名称。我认为将其命名为 T 有助于表明它是类型参数而不是代码中有意义的类:

sealed abstract class FactsQueryAst[T] extends Traversable[T]

所以 FactQueryAst 包含 T 类型的东西，我们希望能够遍历树为每个 t:T 做一些事情。实现的方法是:

def foreach[U](f: T => U): Unit

所以用 T 替换代码中的所有 FactType 并修改 T 的签名，我最终得到:

object FactsQueryAst {
  case class AndNode[T](subqueries: Seq[FactsQueryAst[T]]) extends FactsQueryAst[T] {
    def foreach[U](f: T => U) { subqueries foreach { _.foreach(f) } }
  }
  case class OrNode[T](subqueries: Seq[FactsQueryAst[T]]) extends FactsQueryAst[T] {
    def foreach[U](f: T => U) { subqueries foreach { _.foreach(f) } }
  }
  case class Condition[T](factType: T, value: FactValue) extends FactsQueryAst[T] {
    def foreach[U](f: T => U) { f(factType) }
  }
}

这样工作:

import FactsQueryAst._
case class FactValue(v: String)
val t =
  OrNode(
    Seq(
      AndNode(
        Seq(Condition(1, FactValue("one")), Condition(2, FactValue("two")))),
      AndNode(
        Seq(Condition(3, FactValue("three"))))))
//> t  : worksheets.FactsQueryAst.OrNode[Int] = FactsQueryAst(1, 2, 3)
t.map(i => i + 1)
//> res0: Traversable[Int] = List(2, 3, 4)

当您映射时，显然实现 traversable 会丢失结构，但这对于您的用例来说可能已经足够了。如果您有更具体的需求，可以提出其他问题。

编辑:

事实证明，您的初始版本可能会起作用。这是一个几乎相同的版本，但请注意我在 Condition 中覆盖了 toString。我怀疑如果你覆盖 toString() 你的版本也可以工作:

case class FactValue(v: String)
case class FactType(t: Int)

sealed abstract class FactsQueryAst extends Traversable[FactsQueryAst.Condition]

object FactsQueryAst {
  case class AndNode(subqueries: Seq[FactsQueryAst]) extends FactsQueryAst {
    def foreach[U](f: Condition => U) { subqueries foreach { _.foreach(f) } }
  }
  case class OrNode(subqueries: Seq[FactsQueryAst]) extends FactsQueryAst {
    def foreach[U](f: Condition => U) { subqueries foreach { _.foreach(f) } }
  }
  case class Condition(factType: FactType, value: FactValue)  extends FactsQueryAst {
    def foreach[U](f: Condition => U) { f(this) }
    override def toString() = s"Cond($factType, $value)"
  }
}

尝试打印对象时发生无限递归；这很可能是由于 TraversableLike 看到 Condition 是 Traversable 调用 mkString 调用 addString 调用 foreach然后事情就进入了一个循环。