3

我在 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)
4

3 回答 3

6

让我们重命名FactType一个看起来更像类型参数的东西。我认为命名它只是T有助于表明它是类型参数而不是代码中有意义的类：

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

soFactQueryAst包含类型的东西，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)

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

编辑：

事实证明，您的初始版本可能会起作用。这是一个几乎相同的版本，但请注意我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，然后事情进入了一个循环。

于 2013-06-10T13:44:37.437 回答
1

我将在这个单独的答案中发布关于如何保留结构的答案，因为另一个答案太长了（这个问题出现在你后来的评论中）。虽然，我怀疑使用 Kiama 是一个更好的选择，但这是保留结构并具有类似于 foldLeft、map 和 filter 的操作的方法。我已经制作了FactTypeandFactValue类型参数，以便我可以给出更短的示例，Int并且String它也更通用。

这个想法是您的树结构是使用 3 个构造函数的递归结构：AndNode并OrNode接受序列并Condition接受两​​个参数。我定义了一个折叠函数，它通过需要 3 个函数递归地将此结构转换为另一种类型R，每个构造函数一个：

sealed abstract class FactsQueryAst[T, V] {
  import FactsQueryAst._
  def fold[R](fAnd: Seq[R] => R, fOr: Seq[R] => R, fCond: (T, V) => R): R = this match {
    case AndNode(seq) => fAnd(seq.map(_.fold(fAnd, fOr, fCond)))
    case OrNode(seq) => fOr(seq.map(_.fold(fAnd, fOr, fCond)))
    case Condition(t, v) => fCond(t, v)
  }
  def mapConditions[U, W](f: (T, V) => (U, W)) =
    fold[FactsQueryAst[U, W]](
      AndNode(_),
      OrNode(_),
      (t, v) => {val uw = f(t, v); Condition(uw._1, uw._2) })
}

object FactsQueryAst {
  case class AndNode[T, V](subqueries: Seq[FactsQueryAst[T, V]]) extends FactsQueryAst[T, V]
  case class OrNode[T, V](subqueries: Seq[FactsQueryAst[T, V]]) extends FactsQueryAst[T, V]
  case class Condition[T, V](factType: T, value: V) extends FactsQueryAst[T, V]
}

mapConditions是根据fold实现的。但还有一堆其他功能。这是在行动：

object so {
  import FactsQueryAst._
  val ast =
    OrNode(
      Seq(
        AndNode(
          Seq(Condition(1, "one"))),
        AndNode(
          Seq(Condition(3, "three")))))
  //> ast  : worksheets.FactsQueryAst.OrNode[Int,String] =
  //    OrNode(List(AndNode(List(Condition(1,one))), 
  //                AndNode(List(Condition(3,three)))))

  val doubled = ast.mapConditions{case (t, v) => (t*2, v*2) }

  //> doubled  : worksheets.FactsQueryAst[Int,String] = 
  //    OrNode(List(AndNode(List(Condition(2,oneone))), 
  //                AndNode(List(Condition(6,threethree)))))

  val sums = ast.fold[(Int, String)](
    seq => seq.reduceLeft((a, b) => (a._1 + b._1, a._2 + b._2)),
    seq => seq.reduceLeft((a, b) => (a._1 + b._1, a._2 + b._2)),
    (t, v) => (t, v))
  //> sums  : (Int, String) = (4,onethree)

  val andOrSwitch = ast.fold[FactsQueryAst[Int, String]](
    OrNode(_),
    AndNode(_),
    (t, v) => Condition(t, v))
  //> andOrSwitch  : worksheets.FactsQueryAst[Int,String] = 
  //    AndNode(List(OrNode(List(Condition(1,one))), 
  //                 OrNode(List(Condition(3,three)))))

  val asList = ast.fold[List[(Int, String)]](
    _.reduceRight(_ ::: _),
    _.reduceRight(_ ::: _),
    (t, v) => List((t, v)))
  //> asList  : List[(Int, String)] = List((1,one), (3,three))  
}
于 2013-06-11T06:03:29.277 回答
1

您很有可能需要研究 traversable-builder 模式。它不是那么直截了当，但它使用类似工厂的模式保留了操作之间的结构。我建议你调查一下：

http://docs.scala-lang.org/overviews/core/architecture-of-scala-collections.html

该模式需要在您的伴随对象中实现一个隐式构建器对象以及一些可遍历的实现（例如，使用一些特征foreach和可能一些更高阶的方法来实现）

我希望这对你有用:)

于 2013-06-11T06:33:32.047 回答