map over structure with only partial match

Question

I have a tree-like structure of abstract classes and case classes representing an Abstract Syntax Tree of a small language.

For the top abstract class i've implemented a method map:

abstract class AST {
...
  def map(f: (AST => AST)): AST = {
     val b1 =  this match {
      case s: STRUCTURAL => s.smap(f) // structural node for example IF(expr,truebranch,falsebranch)
      case _ => this // leaf, // leaf, like ASSIGN(x,2)
    }
    f(b1)
  }
...

The smap is defined like:

 override def smap(f: AST => AST) = {
    this.copy(trueb = trueb.map(f), falseb = falseb.map(f))
  }

Now im writing different "transformations" to insert, remove and change nodes in the AST.

For example, remove adjacent NOP nodes from blocks:

def handle_list(l:List[AST]) = l match {
  case (NOP::NOP::tl) => handle_list(tl)
  case h::tl => h::handle_list(tl)
  case Nil => Nil
}

ast.map {
  case BLOCK(listofstatements) => handle_list(listofstatements)
}

If I write like this, I end up with MatchError and I can "fix it" by changing the above map to:

ast.map {
  case BLOCK(listofstatements) => handle_list(listofstatements)
  case a => a
}

Should I just live with all those case a => a or could I improve my map method(or other parts) in some way?

Answer 1

If tree transformations are more than a minor aspect of your project, I highly recommend you use Kiama's Rewriter module to implement them. It implements Stratego-like strategy-driven transformations. It has a very rich set of strategies and strategy combinators that permit a complete separation of traversal logic (which for the vast majority of cases can be taken "off the shelf" from the supplied strategies and combinators) from (local) transformations (which are specific to your AST and you supply, of course).

Answer 2

Make the argument to map a PartialFunction:

def map(f: PartialFunction[AST, AST]): AST = {
  val idAST: PartialFunction[AST, AST] = {case a => a}
  val g = f.orElse(idAST)

  val b1 =  this match {
    case s: STRUCTURAL => s.smap(g)
    case _ => this
  }
  g(b1)
}