j

{-# LANGUAGE GADTs #-}

module PDA (PDA(..), test) where

import Data.Maybe
import Safe

-- state -> top stack symbol -> sequence symbol -> list of resulting PDA states
type Delta state char = state -> Maybe char -> Maybe char -> [(state, [char])]

data PDA state char where
    -- PDA state (state + stack) -> accepting states -> transition function
    PDA :: (Eq state) => (state, [char]) -> [state] -> Delta state char -> PDA state char

test :: PDA state char -> [char] -> Bool
test (PDA start_pda_state accepting_states delta) sequence = helper sequence start_pda_state
    where helper seq@(s:seqr) pda_state = or ((fmap (helper seqr) $ handle_pda_state pda_state $ Just s) ++
                                              (fmap (helper seq) $ handle_pda_state pda_state Nothing))
          helper [] pda_state = or $ accepted pda_state : (fmap (helper []) $ handle_pda_state pda_state Nothing)
          handle_pda_state (st, stack) s = fmap (\(st, chs) -> (st, chs ++ tailSafe stack)) $ delta st (headMay stack) s
          accepted (state, stack) = state `elem` accepting_states && null stack