Scala concepts: State machine

A state machine is the use of `sealed trait` to represent all the possible states of a 'machine' in a hierarchical form

A great example is in the ParenthesesFoldingStateMachine.

What are the benefits of State machine folding, versus tail recursion?

State changes become more evident and you may be able to test sub-sequences and behaviours more easily.

Another possibility that opens up is that you may now support a stream of parentheses (of indeterminate size!) instead of a fixed-length String.

It works particularly well with scanLeft and scanRight and foldLeft and foldRight as well as Tail Recursion.

Simple parser to find text between brackets

sealed trait BracketParser {
  def next(char: Char): BracketParser
}

object BracketParser {
  case object NoBracketFound extends BracketParser {
    override def next(char: Char): BracketParser =
      if (char == '(') CollectingBracket("") else this
  }
  final case class CollectingBracket(textSoFar: String) extends BracketParser {
    override def next(char: Char): BracketParser =
      if (char == ')') CompletedCollection(textSoFar)
      else CollectingBracket(textSoFar + char)
  }
  final case class CompletedCollection(result: String) extends BracketParser {
    override def next(char: Char): BracketParser = this
  }
}

assert(
  "it works (yes?)"
    .foldLeft[BracketParser](BracketParser.NoBracketFound)(_.next(_)) ==
    BracketParser.CompletedCollection("yes?")
)

While this could be implemented simply with a Regular Expression, if you have any more variations, the complexity becomes unmanageable - this is where state machines really help out. Please see ParenthesesFoldingStateMachine for a good example.

Please also see the article: The most important streaming abstraction