How to make tree implemented in Scala useful with higher-order collection functions?

Question

I have a simple tree structure in Scala implemented like this:

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]
}

Are there any relatively simple ways to make this structure work with higher-order functions like map, foldLeft or filter? There's good article about implementing Traversable trait for your own collections (http://daily-scala.blogspot.com/2010/04/creating-custom-traversable.html), but it seems to be overcomplicated for the tree case, or at least I'm missing something principal.

UPD. I tried to implement naive Traversable as below, but it results in infinite loop just for printing the value.

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)}
  }
}

The stack trace for infinite loop looks like 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

I am going to post my answer on how to preserve structure in this separate answer since the other one is getting too long (and the question came into your later comment). Although, I suspect using Kiama is a better choice, here is way to preserve your structure and have operations similar to foldLeft, map and filter. I have made both FactType and FactValue type parameters so that I can give shorter examples with Int and String and also it is more general.

The idea is that your tree structure is a recursive structure using 3 constructors: AndNode and OrNode takes sequences and Condition takes two arguments. I define a fold function that recursively transform this structure into another type R by requiring 3 functions, one for each of the constructors:

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 is implemented in terms of fold. But also a bunch of other functions. Here it is in action:

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))  
}