FSA (finite state automaton) in Scala
Following suggestions from Landei above, and this article on recursive type declarations in Scala, I've come up with a slightly different solution where states are directly modelled as state transitions.

trait StateFunc [ T ] extends PartialFunction [ T, StateFunc [ T ] ]

sealed abstract class Event

case object E0 extends Event
case object E1 extends Event
case object E2 extends Event

class FSA {
  private type State = StateFunc [ Event ]

  private def transitions [ T ] ( pf : PartialFunction [ T, StateFunc [ T ] ] ) = new StateFunc [ T ] {
    def apply( event : T ) = pf ( event )
    def isDefinedAt ( event : T ) = pf.isDefinedAt ( event ) }

  private val ( s0 : State ) = transitions { case E0 =&gt; s1; case E1 =&gt; s2; case E2 =&gt; s0 }
  private val ( s1 : State ) = transitions { case E0 =&gt; s3; case E1 =&gt; s0; case E2 =&gt; s1 }
  private val ( s2 : State ) = transitions { case E0 =&gt; s2; case E1 =&gt; s1; case E2 =&gt; s0 }
  private val ( s3 : State ) = transitions { case E0 =&gt; s3; case E1 =&gt; s3; case E2 =&gt; s1 }

  private var state = s0

  def handle ( e : Event ) { state = state ( e ) } }


I'm not saying that this is better than the other solutions proposed, but I wonder about memory usage. Clearly, as this is a highly recursive construct, if the compiler doesn't do tail-call optimisation, this solution will run out of memory eventually. I have no understanding of the Scala compiler, but I would imagine that in this simple case the tail calls are optimised to ensure constant stack space usage. But what if the transition functions do something more complicated (e.g. possibly throwing exceptions)? Can constant space usage still be guaranteed?

As an aside, is it really necessary to go through so many hoops to define a recursive type? Why can I not simply write e.g. type T = Map [ Int, T ]?

Edit 9.9.2011: I added @tailrec annotations to the program above with the following results: The compiler accepts @tailrec on s0, ..., s3 just fine. But it balks when I annotate the private definition of transitions, which is not surprising. What that means in practise for stack-space usage of this form of implementing FSAs I don't know.