如何将 foldM 与字符串列表一起用作累加器？编写 NFA

Question

我正在尝试让这个 NFA 工作，现在它在一组（列表）状态到另一组状态之间的转换做得很好。但是当我尝试使用 foldM （我也会接受任何其他方法）时，我不能，因为 foldM 的类型是 (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b 而我想要 (Foldable t, Monad m) => ([b] -> a -> m [b]) -> b -> t a -> m b ，如果可能的话。主要问题出在函数 testNFA.

代码如下：

-- NFA file format
-- 1st line: set of initial states
-- last line: set of final states
-- other lines: transitions table entries, each one is of the form:
-- (state, char viewed, set of next states)

module NFA where

  import Control.Monad

  leerFichero :: String -> IO ()
  leerFichero filename = do
                            contenidos <- readFile filename
                            putStrLn contenidos

  data NFA = NFA { intialStates :: [String]
                 , isAccepting :: String -> Bool
                 , transition  :: [String] -> Char -> [String]
                 }

  strToRow :: [String] -> [((String, Char), [String])]
  strToRow str = map crea_tupla por_espacios
    where
      crea_tupla (x:y:xs) = ((x, head y), xs)
      por_espacios = map words str

  leerNFA :: String -> IO ()
  leerNFA filename = do
                      contenidos <- readFile filename
                      --putStr "Cadena:"
                      --cadena <- getLine
                      let lineas = lines $ contenidos
                          i = words $ head lineas
                          a = (`elem` last (map words lineas))
                          nfa = NFA i a (t (strToRow (tail (init lineas))))
                      print $ t (strToRow (tail (init lineas))) ["Q0","Q1"] '#'

  t :: [((String, Char), [String])] -> [String] -> Char -> [String]
  t tab n c = n >>= (\st -> case lookup (st,c) tab of
                              Just x -> x
                              _      -> error "yo k se tio xdxd")

  --not working
  --testNFA :: NFA -> [Char] -> [String]
  --testNFA (NFA i a t) = foldM t i

Answer 1

重写您的代码，使 transition 具有类型 State -> Symbol -> [State]。这确实是 NFA 所具有的：要获得 [State] -> Symbol -> [State] 函数，您需要对这个函数进行联合调用。然后你就可以轻松使用foldM了。

一个例子：

import Control.Monad

type Symbol = Char
type State  = String

data NFA = NFA { initialState :: State
               , isAccepting  :: State -> Bool
               , transition   :: State -> Symbol -> [State] }

-- https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton#Example
exampleNFA :: NFA
exampleNFA = NFA { initialState = "p"
                 , isAccepting  = (== "q")
                 , transition   = exampleTransition }

exampleTransition :: State -> Symbol -> [State]
exampleTransition "p" '0' = ["p"]
exampleTransition "p" '1' = ["p", "q"]
exampleTransition "q" '0' = []
exampleTransition "q" '1' = []

runNFA :: NFA -> String -> [State]
runNFA (NFA init _ trans) = foldM trans init

main = print $ runNFA exampleNFA "01101"

如何将 foldM 与字符串列表一起用作累加器？编写 NFA

How to use foldM with a list of strings as accumulator? programming a NFA

monads

haskell

list

fold