potong potong - 16 days ago 7
Python Question

Represent Nondeterministic Finite State Machine Simulator in Haskell

I am following "programming languages" on Udacity and trying to represent the problem sets in Haskell. The answers are written in Python:

edges = {(1,"a") : [2,3]
,(2,"a") : [2]
,(3,"b") : [3,4]
,(4,"c") : [5]}

accepting = [2,5]

def nfsmSim(string, current, edges, accepting):
if string == "":
return current in accepting
else:
letter = string[0]
key = (current, letter)
if key in edges:
rest = string[1:]
states = edges[key]
for state in states:
if nfsmSim(rest, state, edges, accepting):
return True
return False


The starting state is always the first state i.e.
current = 1
.

Strings such as
"aaa"
or
"abc"
are accepted whilst
"abb"
or
"aabc"
or rejected.

My attempt at rewriting using Haskell:

nfsmSim [] c _ = [c]
nfsmSim xs c es = [concat $ nfsmSim (tail xs) s es | (k,ss) <- es, s <- ss, x <- xs, k==(c,x)]


I want to return a list of integers which represent the last state at the end of the input string and then
filter
these against the accepting states and use
any
to get a final
True
or
False
.

I realise this is not probably the Haskell way to do this and that there is probably a better
wholemeal
solution. However as a beginner I am struggling with mondadic mechanism and most likely the recursive nature of this problem.

Please point me in the right direction possibly using the
do
notation rather than the list comprehension.

Answer

Let us think about the type first. Your Python function has the following type, more or less:

type State   = Int
type Map k v = [(k,v)]

nfsmSim :: String -> State -> Map (Int, Char) [State] -> [State] -> Bool
nfsmSim string current edges accepting = …

We can use pattern matching for the empty string case:

nfsmSim :: String -> State -> Map (Int, Char) [State] -> [State] -> Bool
nfsmSim "" current _ accepting = current `elem` accepting

For the non-empty case, we do the same as your Python code:

nfsmSim (x:xs) current edges accepting =
    let rest   = xs
        states = [s | (k,v) <- edges, k == (current,x), s <- v]
    in or [nfsmSim rest state edges accepting | state <- states]

However, that's not really easy to work with. Instead, let us write nfsmSim as higher order function and change the order of arguments:

nfsmSim :: (State -> Char -> [State])
        -> (State -> Bool)
        -> String
        -> State
        -> Bool

Now, instead of a list of edges, we have to provide a function that returns a (possible empty) list of states for a given state and character, and instead of a list of accepting states, we provide a function that returns True on those states.

For the empty string case, not too much changes:

nfsmSim advance accept "" current = accept current

We simply use our State -> Bool to check whether our current state is acceptable.

However, now that our State is the last parameter of nfsmSim, we can use currying to use your any approach:

nfsmSim advance accept (x:xs) current = 
    any (nfsmSim advance accept xs) (advance current x)

Note that it's kind of clunky to carry all arguments along. You would usually write a worker for that:

nfsmSim :: (a -> b -> [a]) -> (a -> Bool) -> [b] -> a -> Bool
nfsmSim advance accept string current = go string current
  where
    go []     c = accept c
    go (x:xs) c = any (go xs) (advance c x)

By the way, you can still use "edges" and "accepting" with the last variant,

nfsmSimAccept string current edges accepting =
   let accept  c   = c `elem` accepting
       advance c x = [s | (k,v) <- edges, k == (c,x), s <- v]
   in nfsmSim advance accept string current

which shows that the higher order function is more flexible.