ハスケルの非決定論的有限状態機械シミュレータを表現する

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"や​​など

文字列は"abb"または"aabc"ながら、承認または拒否されています。

書き換えでの私の試み使用ハスケル：

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

まずタイプを考えてみましょう。

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

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

私たちは、空の文字列の場合のパターンマッチングを使用することができます：あなたのPythonの関数は次の型、多かれ少なかれあり

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を使用しています。それは一種の不格好に沿ってすべての引数を運ぶためだと

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

注：

しかし、今、私たちのStateがnfsmSimの最後のパラメータであることを、私たちはあなたのanyアプローチを使用するようにカリー化を使用することができます。高階関数ことを示している

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 

ところで

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) 

、あなたはまだ最後の変種で「エッジ」と「受諾」を使用することができ、

：あなたは通常、そのために労働者を記述しますより柔軟性があります。

当社は、ステートマシンを表現するためにHaskellのData.SetとData.Mapライブラリを使用することができます。

Answer 2

は、ここに私はHaskellっぽい方法です。

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

のは、私たちの状態マシンにはいくつかのデータ型を定義してみましょう：

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 

私たちは以下のようなものを、マシンを定義

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

この関数はを返しますでは、モナドや表記を使用する大きな理由はありません。しかし、Boolの代わりにMaybe()タイプを使用すると、Just()がTrueを表し、NothingがFalseを表す場合、そのような解決策が可能です。

Answer 3

まず、私が知っているように、「非有限状態機械」のようなものはありません。あなたが書いたことから判断すると、それは「非決定的有限オートマトン（NFA）」に関することです。

第1変種。

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