The types should be known at compile time, but you can do runtime checks to see if your returned object is based on a particular trait.

Simple example based on your classes:

/** your classes here */

case class NullExpr() extends Expression

scala> def derive(l:List[Expression]) = l.fold(Epsilon()) {
     | (acc, elem) => if (!acc.isInstanceOf[BNF] || !elem.isInstanceOf[BNF]) 
     | NullExpr() else elem }
derive: (l: List[Expression])Expression

scala> derive(List(Epsilon(), Regex("abcd")))
res8: Expression = Regex(abcd)

scala> res8.isInstanceOf[BNF]
res9: Boolean = true

scala> derive(List(NullExpr(), Epsilon()))
res10: Expression = NullExpr()

scala> res10.isInstanceOf[BNF]
res11: Boolean = false


Now I want to specify that a Conc(atenation) and Alt(ernate) have the trait BNF if and only if all Expressions in list have the trait BNF.

It isn't possible for a single class to sometimes extend a trait and sometimes not. You could have separate classes Conc and ConcBNF, and similarly for Alt. Instead, I'd just do

sealed abstract class Expression {
  def isBNF: Boolean

abstract class Literal extends Expression {
  def isBNF = true

case class Conc(list: List[Expression]) extends Expression {
  def isBNF = list.all(_.isBNF) // or val isBNF if you want to avoid recalculation

// and so on

Related Query

More Query from same tag