Представить недетерминированный конечный машинный симулятор машины в Haskell

Question

Я следую «языкам программирования» по Udacity и пытаюсь представить наборы задач в Haskell. Ответы записываются в Python:

edges = {(1,"a") : [2,3] 
     ,(2,"a") : [2] 
     ,(3,"b") : [3,4] 
     ,(4,"c") : [5]} 

accepting = [2,5] 

def nfsmSim(string, current, edges, accepting): 
    if string == "": 
     return current in accepting 
    else: 
     letter = string[0] 
     key = (current, letter) 
     if key in edges: 
      rest = string[1:] 
      states = edges[key] 
      for state in states: 
       if nfsmSim(rest, state, edges, accepting): 
        return True 
     return False 

Исходное состояние всегда первое состояние, т.е. current = 1.

Строки, такие как "aaa" или "abc" принимаются в то время как "abb" или "aabc" или отклонено.

Моя попытка перезаписи с помощью Haskell:

nfsmSim [] c _ = [c] 
nfsmSim xs c es = [concat $ nfsmSim (tail xs) s es | (k,ss) <- es, s <- ss, x <- xs, k==(c,x)] 

Я хочу вернуть список целых чисел, которые представляют собой последнее состояние в конце входной строки, а затем filter они против принимающих государств и использовать any для получить окончательный True или False.

Я понимаю, что это, вероятно, не способ Haskell сделать это и что, вероятно, есть лучшее решение wholemeal. Однако, как новичок, я борюсь с механизмом мондадизма и, скорее всего, рекурсивным характером этой проблемы.

Пожалуйста, укажите меня в правильном направлении, возможно, используя нотацию do, а не список.

Answer 1

Давайте подумаем о типе в первую очередь. Ваша функция Python имеет следующий вид, более или менее:

type State = Int 
type Map k v = [(k,v)] 

nfsmSim :: String -> State -> Map (Int, Char) [State] -> [State] -> Bool 
nfsmSim string current edges accepting = … 

Мы можем использовать шаблон соответствия для пустой строки случая:

nfsmSim :: String -> State -> Map (Int, Char) [State] -> [State] -> Bool 
nfsmSim "" current _ accepting = current `elem` accepting 

Для непустого случае, мы делаем то же самое как ваш код Python:

nfsmSim (x:xs) current edges accepting = 
    let rest = xs 
     states = [s | (k,v) <- edges, k == (current,x), s <- v] 
    in or [nfsmSim rest state edges accepting | state <- states] 

Однако с этим работать нелегко. Вместо этого, давайте писать nfsmSim как функции высшего порядка и изменить порядок аргументов:

nfsmSim :: (State -> Char -> [State]) 
     -> (State -> Bool) 
     -> String 
     -> State 
     -> Bool 

Теперь, вместо списка ребер, мы должны обеспечить функцию, которая возвращает (возможно пустой) список состояний для заданное состояние и характер, а вместо списка принимающих состояний мы предоставляем функцию, которая возвращает True в этих состояниях.

пустой строки случае, не слишком много изменений:

nfsmSim advance accept "" current = accept current 

Мы просто используем наш State -> Bool, чтобы проверить, является ли приемлемым нашим нынешним состоянием.

Однако теперь, когда наш State последний параметр nfsmSim, мы можем использовать выделки использовать any подход:

nfsmSim advance accept (x:xs) current = 
    any (nfsmSim advance accept xs) (advance current x) 

Обратите внимание, что это своего рода неуклюжим, чтобы нести все аргументы вместе.Вы, как правило, написать работник для этого:

nfsmSim :: (a -> b -> [a]) -> (a -> Bool) -> [b] -> a -> Bool 
nfsmSim advance accept string current = go string current 
    where 
    go []  c = accept c 
    go (x:xs) c = any (go xs) (advance c x) 

Кстати, вы все еще можете использовать «ребро» и «принимающий» с последним вариантом,

nfsmSimAccept string current edges accepting = 
    let accept c = c `elem` accepting 
     advance c x = [s | (k,v) <- edges, k == (c,x), s <- v] 
    in nfsmSim advance accept string current 

, который показывает, что функции более высокого порядка является более гибким.

Answer 2

Вот мой Haskell-иш способ:

Мы можем использовать Data.Set и Data.Map библиотеки Haskell, чтобы представлять нашу государственную машину.

import qualified Data.Map as M 
import qualified Data.Set as S 

Давайте определим некоторые типы данных для нашей государственной машины:

type State = Int 
type Edge = (State, Char) 
type Machine = (M.Map Edge (S.Set State), S.Set State) 

Определим машину таким образом:

myMachine :: Machine 
myMachine = (M.fromList 
    [ ((1, 'a'), S.fromList [2, 3]) 
    , ((2, 'a'), S.fromList [2 ]) 
    , ((3, 'b'), S.fromList [3, 4]) 
    , ((4, 'c'), S.fromList [5 ]) 
    ] , S.fromList [2, 5]) 

мы можем запустить машину, как это:

runMachine :: String -> Machine -> State -> Bool 
runMachine "" (_, acceptingStates) currentState = 
    S.member currentState acceptingStates 
runMachine (ch:rest) machine@(edges, _) currentState = 
    case M.lookup (currentState, ch) edges of 
     Nothing -> False 
     Just nextStates -> 
      or $ S.map (runMachine rest machine) nextStates 

Поскольку функция возвращает Bool, нет никакой причины использовать монаду или нотацию. Однако такое решение возможно, если мы используем тип Maybe() вместо Bool, где Just() представляет True и Nothing представляет False.

Answer 3

Прежде всего, как я знаю, нет такой вещи, как «Non Finite State Machine». Судя по тому, что вы написали, я понял, что речь идет о «недетерминированном конечном автомате (NFA)».

Первый вариант.

nfa :: String -> Int -> [((Int, Char), [Int])] -> [Int] -> Bool 
nfa  [] cur  _ acc = cur `elem` acc 
nfa (c:rest) cur edges acc 
    | Just states <- lookup (cur, c) edges = any (\state -> nfa rest state edges acc) states 
    | otherwise       = False 

edges = 
    [ ((1, 'a'), [2, 3]) 
    , ((2, 'a'), [2]) 
    , ((3, 'b'), [3, 4]) 
    , ((4, 'c'), [5]) 
    ] 

accepting = [2, 5] 

main = do 
    print $ nfa "aaa" 1 edges accepting 
    print $ nfa "abc" 1 edges accepting 
    print $ nfa "abb" 1 edges accepting 
    print $ nfa "aabc" 1 edges accepting 

выход будет:

True 
True 
False 
False 

Второй вариант:

import Control.Monad 
import Data.Maybe 

nfa2 :: String -> Int -> [((Int, Char), [Int])] -> [Int] -> [Int] 
nfa2  [] cur  _ acc = guard (cur `elem` acc) >> return cur 
nfa2 (c:rest) cur edges acc = do 
    state <- fromMaybe mzero $ lookup (cur, c) edges 
    nfa2 rest state edges acc 

edges = 
    [ ((1, 'a'), [2, 3]) 
    , ((2, 'a'), [2]) 
    , ((3, 'b'), [3, 4]) 
    , ((4, 'c'), [5]) 
    ] 

accepting = [2, 5] 

main = do 
    print $ nfa2 "aaa" 1 edges accepting 
    print $ nfa2 "abc" 1 edges accepting 
    print $ nfa2 "abb" 1 edges accepting 
    print $ nfa2 "aabc" 1 edges accepting 

выход будет:

[2] 
[5] 
[] 
[]