accepting/rejecting haskell 中的下推自动机

Question

我正在尝试创建一个签入 Haskell 的下推自动机。基本上，一个接受 (start_state, final_state, set_of_rules) and a string 的函数。如果该 PDA 接受该字符串，它应该 return Accepted，否则 Rejected。

这是我目前拥有的：

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]]]

最后一行是我的逻辑中断的地方我想解释一下：

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

这需要一组规则 (tt) 并列出我可能在当前状态 (cs) 和字符串头部匹配的情况下使用的所有规则。这非常有效并列出了所有可能的动作。我想再次通过此函数获取此列表中的每个元素并运行它。当我达到我的基本情况时，我 return 根据堆栈状态接受或拒绝。

我希望看到的是一个充满 Reject 的列表，因为我实际上还没有使用堆栈。

我一直收到 Couldn't match type ‘[Result]’ with ‘Result’ 编译错误，我无法修复它。非常感谢任何帮助

Answer 1

问题是在递归子句中：

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

您违反了类型合同。实际上 runs 应该是 return 的 Result 列表。但是在你的表达式中，你构建了一个 runs 的结果列表（好吧 runs z (d, xs, e) 的列表，这意味着这个列表理解正在构建 Results 的列表，而不是 Results 的列表结果列表。

因此我们需要将这些子列表 "concatenate" 合并为一个平面列表，例如 concat :: [[a]] -> [a]，以及：

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) = <b>concat</b> [runs z (d,xs,e) | m@((a,b,c),(d,e)) <- [xf | xf@((a,b,c),(d,e)) <- tt, a == cs, b == [x]]]

accepting/rejecting haskell 中的下推自动机

accepting/rejecting Pushdown automata in haskell

recursion

haskell

pushdown-automaton