accepting/rejecting Pushdown automata in haskell

Question

I am trying to create a Pushdown Automata checking in Haskell. Basically, a function which takes (start_state, final_state, set_of_rules) and a string. It should return Accepted if the string is accepted by this PDA and Rejected otherwise.

This is what I have so far:

type Transition = ((Int,String,String),(Int,String))

type Configuration = (Int,String,String)

type PDA = (Int,[Int],[Transition])

data Result = Accept | Reject | Jj deriving Show

run :: PDA -> String -> [Result]
run (ss,fs,tr) xs = runs (ss,fs,tr) (ss,xs,"")

runs :: PDA -> Configuration -> [Result]
-- When string and stack empty accept
runs _ (_,[],[]) = [Accept]
-- If string empty and stack not empty, reject
runs _ (_,[],_) = [Reject]
runs z@(ss,fs,tt) (cs,(x:xs),st) = [runs z (d,xs,e) | m@((a,b,c),(d,e)) <- [xf | xf@((a,b,c),(d,e)) <- tt, a == cs, b == [x]]]

The very last line is where my logic breaks I'd like to explain it a bit:

[xf | xf@((a,b,c),(d,e)) <- tt, a == cs, b == [x]]

This takes a set of rules (tt) and lists all rules I could possibly use where the current state (cs) and head of my string match. This works perfectly and lists all possible moves. I'd like to take every element of this list and run it through this function again. When I reach my base case I return Accept or Reject based on the stack state.

What I am expecting to see is a list full of Reject because I am not actually working with the stack yet.

I keep getting Couldn't match type ‘[Result]’ with ‘Result’ compile error all the time and I just can't fix it. Any help is really appreciated

Answer 1

The problem is that in the recursive clause:

runs :: PDA -> Configuration -> [Result]
-- ...
runs z@(ss,fs,tt) (cs,(x:xs),st) = [runs z (d,xs,e) | ... ]

You violate a type contract. Indeed runs is supposed to return a list of Results. But here in your expression you construct a list of outcomes of runs (well a list of runs z (d, xs, e), this thus means that this list comprehension is constructing a list of list of Results, not a list of results.

We thus need to "concatenate" these sublists into one flat list, for example with concat :: [[a]] -> [a], with:

runs :: PDA -> Configuration -> [Result]
-- When string and stack empty accept
runs _ (_,[],[]) = [Accept]
-- If string empty and stack not empty, reject
runs _ (_,[],_) = [Reject]
runs z@(ss,fs,tt) (cs,(x:xs),st) = concat [runs z (d,xs,e) | m@((a,b,c),(d,e)) <- [xf | xf@((a,b,c),(d,e)) <- tt, a == cs, b == [x]]]