Notes on learning haskell (1)

----------------------------------
--   A DFA that accepts (abc)*
----------------------------------
--   State transition table:
----------------------------------
--    (0, 'a')  -> (True, 1)
--    (1, 'b')  -> (True, 2)
--    (2, 'c')  -> (True, 0)
--    otherwise -> (False, (-1))
----------------------------------

data DFA s a = DFA { runDFA:: s -> (a, s) }

instance Monad (DFA s) where
    return a = DFA $ \s -> (a, s)
    m >>= f  = DFA $ \s ->
        let (a, s') = runDFA m s
            n = f a
        in  runDFA n s'

onOneChar c = DFA $ \state -> case (state, c) of
    (0, 'a') -> (True, 1)
    (1, 'b') -> (True, 2)
    (2, 'c') -> (True, 0)
    _        -> (False, (-1))

parse [] = do return ()
parse (c:cs) = do
    shouldContinue <- onOneChar c
    if shouldContinue then parse cs else return ()

acceptable str = let (_, state) = runDFA (parse str) 0 in state == 0
Advertisements
This entry was posted in Programming. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s