module FSM where

type FSM alph state = (state, [state], TransRel alph state)

type TransRel alph state = [((state,alph),state)]


step :: (Eq state, Eq alph) =>
        FSM alph state -> alph -> (state -> [state])
step (start, acc, tr) a s =
  [ s' | (p,s') <- tr, p == (s,a)]

stepD :: (Eq state, Eq alph) =>
        FSM alph state -> alph -> (state -> Maybe state)
stepD (start, acc, tr) a s = lookup (s,a) tr

steps :: (Eq state, Eq alph) =>
        FSM alph state -> [alph] -> (state -> [state])
steps fsm [] s = [s]
steps fsm (a:as) s =
  [ s''
  | s' <- step fsm a s
  , s'' <- steps fsm as s'
  ]


accept :: (Eq state, Eq alph) =>
          FSM alph state -> [alph] -> Bool
accept fsm@(start,acc,tr) w = not $ null
  [ s' |
   s' <- steps fsm w start,
   s' `elem` acc
  ]

fsm1 :: FSM Char Int
fsm1 = (1,[2,3],
  [((1,'a'),2)
  ,((2,'b'),1)
  ,((1,'a'),4)
  ,((4,'a'),4)
  ,((4,'c'),3)
  ])


fsm2 :: FSM Char Int
fsm2 = (1,[2,3],
  [((1,'a'),2)
  ,((2,'b'),1)
  ,((1,'d'),4)
  ,((4,'a'),4)
  ,((4,'c'),3)
  ])