Skip to content

Instantly share code, notes, and snippets.

@SethTisue
Created May 6, 2011 23:32
Show Gist options
  • Save SethTisue/960003 to your computer and use it in GitHub Desktop.
Save SethTisue/960003 to your computer and use it in GitHub Desktop.
sample DFA (deterministic finite automaton) implementation in 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!")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment