如何使用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

因此FactType,在代码中替换所有代码T并修改签名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)

显然,当您映射时,实现可遍历会丢失结构,但这可能足以满足您的用例.如果您有更具体的需求,可以提出另一个问题.

编辑:

事实证明你的初始版本可能会起作用.这是一个几乎相同的版本,但请注意,我重写toString在Condition.我怀疑如果你覆盖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,然后东西进入循环.