Как использовать foldl / foldr на строках в автомате? - PullRequest
Новая
       19

Как использовать foldl / foldr на строках в автомате?

0 голосов
/ 17 мая 2019

Мне нужно создать конечный автомат, который равен функции поиска текстового редактора.

Мне нужно использовать foldl / foldr, чтобы применить функцию к каждому символу строки.

IУ меня есть несколько состояний, с которыми я должен работать: 

type State = Int

start :: State
start = 0

accept :: State
accept = (-2)

reject :: State
reject = (-1)

И у меня есть тип synonim: type Definition = [(State, Char -> State)]

Функция должна выглядеть следующим образом: fsm :: Definition -> String -> Bool

Мой код выглядит следующим образом: 

transition :: Char -> State -> (Char -> State)

transition x y z
 | x == z = y
 | x == '*' = y
 | otherwise = reject

transitions :: [(Char, State)] -> (Char -> State)

transitions ((a,b):xs) e 
 | a == e || a == '*' = b
 | a /= e || a /= '*' = transitions xs e
 | otherwise = reject


step :: Definition -> State -> Char -> State

step ((a,b):xs) e f
 | a == e = b f
 | a /= e = step xs e f
 | otherwise = reject

Он имеет начальное состояние, применяет функцию перехода или переходов, и, если он принят, следующее принятое состояние принимается.

Вот несколько тестов, которые я должен протестировать: 

fsm [ (start, transition '*' accept)] "x" == True

fsm [ (start, transition 'a' 1)
    , (1, transition 'l' 2)
    , (2, transition '*' accept)
    ] "alma" == True

fsm [ (start, transition '*' 1)
    , (1, transition '*' 2)
    , (2, transition 'x' 3)
    , (3, transition '*' accept)
    ] "taxi" == True

fsm [ (start, transitions [('\n',accept), ('*', 1)])
    , (1, transition '*' start) 
    ] "aa\n" == True

1 Ответ

0 голосов
/ 18 мая 2019

Если вы заполните начальное состояние и строку для обработки в foldl, типы в основном подразумевают остальное: 

-- foldl :: Foldable t => (State -> Char -> State) -> State -> [Char] -> State
fsm def str = foldl x start str

Здесь x должен иметь тип State -> Char -> State и давать вам следующее состояние с учетом текущего и следующего символа, что и делает ваша функция step с Definition, что у вас есть. Это дает вам: 

fsm def str = foldl (step def) start str :: State

Теперь у вас есть State, но вам нужно Bool сказать, если оно принято, что просто сравнение: 

fsm def str = foldl (step def) start str == accept
...