fsa.scala

package fsa

import state.State

sealed trait Alphabet
case object A extends Alphabet
case object B extends Alphabet

sealed trait FSAState
case object Q0 extends FSAState
case object Q1 extends FSAState
case object Q2 extends FSAState

case class FSA(q: FSAState) {
  def advance(a: Alphabet): State[FSA, Unit] =
    State.set(FSA((a, this.q) match {
      case (A, Q0) => Q1
      case (A, Q1) => Q0
      case _ => Q2
    }))

  def accepting: Boolean =
    this.q match {
      case Q1 => true
      case _ => false
    }
}

object FSA {
  private def simulate(input: List[Alphabet]): State[FSA, Boolean] =
    State.sequence(input.map(a => State.get.flatMap((m: FSA) => m.advance(a))))
      .flatMap((_: List[Unit]) => State.get.map((m: FSA) => m.accepting))

  def recognize(input: List[Alphabet]): Boolean =
    simulate(input).run(FSA(Q0))._1

  def main(args: Array[String]): Unit = {
    println(FSA.recognize(List()))
    println(FSA.recognize(List(A)))
    println(FSA.recognize(List(A, A)))
    println(FSA.recognize(List(A, A, A)))
    println(FSA.recognize(List(A, A, B, B, A)))
  }
}