term.scala

trait Term[T <: Term[T]]
trait App[T <: Term[T]] extends Term[T] { def f: T; def x: T }
trait Var[T <: Term[T]] extends Term[T] { def s: String }

sealed trait DetTerm extends Term[DetTerm]
case class DetApp(f: DetTerm, x: DetTerm) extends DetTerm
case class DetVar(s: String) extends DetTerm

sealed trait NonDetTerm extends Term[NonDetTerm] {
  def det: Stream[DetTerm]
}

case class NonDetApp(f: NonDetTerm, x: NonDetTerm) extends NonDetTerm {
  def det = f.det.flatMap(detf => x.det.map(DetApp(detf, _)))
}

case class NonDetAmb(a: NonDetTerm, b: NonDetTerm) extends NonDetTerm {
  def det = a.det ++ b.det
}

case class NonDetVar(s: String) extends NonDetTerm {
  def det = Stream(DetVar(s))
}