Formation of variations of nested classes

Question

So, I got something like this:

abstract class Term case class App(f:Term,x:Term) extends Term case class Var(s:String) extends Term case class Amb(a:Term, b:Term) extends Term //ambiguity 

And the term may look like this:

 App(Var(f),Amb(Var(x),Amb(Var(y),Var(z)))) 

So, I need all the options that are denoted by the Amb class. This is used to represent an ambiguous parse tree, and I want to print all possible options and choose the right one. In this example, I will need:

 App(Var(f),Var(x)) App(Var(f),Var(y)) App(Var(f),Var(z)) 

What is the best way to create these changes in scala? Efficiency would be nice, but this is not really a requirement. If possible, I like to refrain from reflection.

Answer 1

Scala provides pattern matching to solve these problems. The solution will look like this:

 def matcher(term: Term): List[Term] = { term match { case Amb(a, b) => matcher(a) ++ matcher(b) case App(a, b) => for { va <- matcher(a); vb <- matcher(b) } yield App(va, vb) case v: Var => List(v) } } 

Answer 2

You can do this quite cleanly with a recursive function that traverses the tree and expands the ambiguities:

 sealed trait Term case class App(f: Term, x: Term) extends Term case class Var(s: String) extends Term case class Amb(a: Term, b: Term) extends Term def det(term: Term): Stream[Term] = term match { case v: Var => Stream(v) case App(f, x) => det(f).flatMap(detf => det(x).map(App(detf, _))) case Amb(a, b) => det(a) ++ det(b) } 

Note that I use a sealed slash instead of an abstract class to take advantage of the compiler's ability to check for completeness.

It works as expected:

 scala> val app = App(Var("f"), Amb(Var("x"), Amb(Var("y"), Var("z")))) app: App = App(Var(f),Amb(Var(x),Amb(Var(y),Var(z)))) scala> det(app) foreach println App(Var(f),Var(x)) App(Var(f),Var(y)) App(Var(f),Var(z)) 

If you can change the Term API, you can more or less equivalently add def det: Stream[Term] .

Answer 3

Since my abstract syntax is pretty big (and I have a lot), and I tried my luck with Kiama. So, here is the version of Travis Brown and Mark posted with Kiama.

This is not very good, but I hope it works. Comments are welcome.

  def disambiguateRule: Strategy = rule { case Amb(a: Term, b: Term) => rewrite(disambiguateRule)(a).asInstanceOf[List[_]] ++ rewrite(disambiguateRule)(b).asInstanceOf[List[_]] case x => val ch = getChildren(x) if(ch.isEmpty) { List(x) } else { val chdis = ch.map({ rewrite(disambiguateRule)(_) }) // get all disambiguate children //create all combinations of the disambiguated children val p = combinations(chdis.asInstanceOf[List[List[AnyRef]]]) //use dup from Kiama to recreate the term with every combination val xs = for { newchildren <- p } yield dup(x.asInstanceOf[Product], newchildren.toArray) xs } } def combinations(ll: List[List[AnyRef]]): List[List[AnyRef]] = ll match { case Nil => Nil case x :: Nil => x.map { List(_) } case x :: xs => combinations(xs).flatMap({ ys => x.map({ xx => xx :: ys }) }) } def getChildren(x: Any): List[Any] = { val l = new ListBuffer[Any]() all(queryf { case a => l += a })(x) l.toList }