在 Haskell 中表示非确定性有限状态机模拟器

Question

我在 Udacity 上关注 "programming languages"，并试图在 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)]

我想要 return 一个整数列表，代表输入字符串末尾的最后状态，然后 filter 这些与接受状态相对应，并使用 any 得到最后的 True 或 False.

我意识到这可能不是 Haskell 的方法，可能有更好的 wholemeal 解决方案。然而，作为一个初学者，我正在为 mondadic 机制而苦苦挣扎，而且很可能是这个问题的递归性质。

请使用 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

现在，我们必须提供一个函数，而不是边缘列表，该函数 returns 给定状态和字符的状态列表（可能为空），而不是接受状态列表，我们提供了一个 returns 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)

顺便说一下，您仍然可以使用 "edges" 和 "accepting" 最后一个变体，

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-ish 方法：

我们可以使用 haskell 的 Data.Set 和 Data.Map 库来表示我们的状态机。

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

因为函数 returns a Bool，没有很好的理由使用 monad 或 do-notation。然而，如果我们使用类型 Maybe () 代替 Bool，这样的解决方案是可能的，其中 Just () 表示 True，Nothing 表示 False。

Answer 3

首先，据我所知，没有"Non Finite State Machine"这样的东西。从你写的来看，我意识到它是关于 "Nondeterministic finite automaton (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]
[]
[]

在 Haskell 中表示非确定性有限状态机模拟器

Represent Nondeterministic Finite State Machine Simulator in Haskell

python

monads

recursion

haskell

functional-programming