sample DFA (deterministic finite automaton) implementation in Scala

StateMachine.scala

// implements this DFA:                                                                                                                
//   en.wikipedia.org/wiki/File:DFAexample.svg                                                                                         
// as described here:                                                                                                                  
//   en.wikipedia.org/wiki/Finite-state_machine#Acceptors_and_recognizers                                                              

// We have a few representational choices here:                                                                                        
// - We can have an explicit EOF, or not.                                                                                              
//   (I chose yes.)                                                                                                                    
// - We can represent success and failure as states, or not.                                                                           
//   (I chose to use Either instead.)                                                                                                  

sealed trait Input
case object Zero extends Input
case object One extends Input
case object EOF extends Input

trait State {
  def next(i: Input): Either[Boolean, State]
}

case object S1 extends State {
  def next(i: Input) = i match {
    case Zero => Right(S2)
    case One => Right(S1)
    case EOF => Left(true)
  }
}
case object S2 extends State {
  def next(i: Input) = i match {
    case Zero => Right(S1)
    case One => Right(S2)
    case EOF => Left(false)
  }
}

def process(s: State, is: List[Input]): Boolean =
  s.next(is.head).fold(identity, process(_, is.tail))

  // // or, to make it @tailrec:                                                                                                       
  // s.next(is.head) match {                                                                                                           
  //   case Left(b) => b                                                                                                               
  //   case Right(s) => process(s, is.tail)                                                                                            
  // }                                                                                                                                 
                                                                                                                                       
def test(is: List[Input]) {
  val expected = is.count(_ == Zero) % 2 == 0
  val actual = process(S1, is :+ EOF)
  require(expected == actual)
}


test(List())
test(List(Zero))
test(List(One))
test(List(Zero, One))
test(List(One, Zero))
test(List(Zero, Zero))
test(List(One, One))
test(List(Zero, Zero, Zero))
test(List(Zero, Zero, One, Zero))
test(List(Zero, Zero, Zero, Zero))
test(List(Zero, One, Zero, Zero, Zero))

println("success!")