Building variations of nested case 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 a Term may look like this:

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

So what I need is all variations that are indicated by the Amb class. This is used to represent a ambiguous parse forest and I want to type check each possible variation and select the right one. In this example I would need:

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

Whats the best way to create these variations in scala? Efficiency would be nice, but is not really requirement. If possible I like to refrain from using reflection.

Answer 1

Scala provides pattern matching solve these kinds of problems. A solution would look like:

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 pretty cleanly with a recursive function that traverses the tree and expands 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'm using a sealed trait instead of an abstract class in order to take advantage of the compiler's ability to check exhaustivity.

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 could more or less equivalently add a def det: Stream[Term] method there.