принимать / отклонять автоматы Pushdown в haskell - PullRequest
Новая
       43

принимать / отклонять автоматы Pushdown в haskell

0 голосов
/ 17 ноября 2018

Я пытаюсь создать проверку автоматов Pushdown в Haskell. В основном, функция, которая принимает (start_state, final_state, set_of_rules) and a string. Он должен вернуть 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) и заголовок моей строки совпадают. Это работает отлично и перечисляет все возможные ходы. Я хотел бы взять каждый элемент этого списка и снова запустить его через эту функцию. Когда я достигаю своего базового случая, я возвращаю Accept или Reject в зависимости от состояния стека.

Я ожидаю увидеть список, полный Reject, потому что на самом деле я еще не работаю со стеком.

Я постоянно получаю Couldn't match type ‘[Result]’ with ‘Result’ ошибку компиляции, и я просто не могу ее исправить. Любая помощь очень ценится

1 Ответ

0 голосов
/ 17 ноября 2018

Проблема в том, что в рекурсивном предложении: 

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

Вы нарушаете типовой контракт.Действительно, runs должен возвращать список Result с.Но здесь, в вашем выражении, вы строите список результатов runs (хорошо, список runs z (d, xs, e), это, таким образом, означает, что это понимание списка строит список списка Results, а не список результатов.

Таким образом, нам необходимо «объединить» эти подсписки в один плоский список, например, с 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]]]
...