递归函数中的类型匹配和 IO 问题

Question

我遇到了一些问题，找不到原因。我目前正在使用最新版本的 GHCi 便携式 - 但面对事实：这是我第一次使用 Haskell，所以像往常一样，问题可能出在用户身上，而不是系统...

出现的问题包括：

我不确定我是否正确区分了 let x = 0 和 x <- 0。我知道 let 是与纯函数一起使用，<- 与副作用（IO）一起使用？请有人再给我解释一下。
我的类型不匹配，即 String 和 (String,[Char])（有时还有其他...）。编译器告诉我 String 是预期的，尽管我明确地将函数定义为 (String,String)。这是怎么回事？我是不是在某个地方弄错了模式匹配？
递归没有按预期工作（即显然根本不工作）。如果有人能帮助我，我将不胜感激。

这是我想要做的：
我正在尝试编写一个小程序来实现接受单词的有限状态机。这意味着它需要一组状态，其中之一是开始状态、接受状态列表和一些转换规则。（表示可能的输入和状态的字母有些隐含。）我不想在这里详细介绍 FSM。

但是，这就是我想出的一种定义此类 FSM 的方法：

"a(b+|c+)"
"start"
["b","c"]
[
("start",   [('a',"a"),                         ('_',"reject")]),
("a",       [           ('b',"b"),  ('c',"c"),  ('_',"reject")]),
("b",       [           ('b',"b"),              ('_',"reject")]),
("c",       [                       ('c',"c"),  ('_',"reject")]),
("reject",  [                                   ('_',"reject")])
]

在第一行中，我们对 FSM 应该接受的内容进行了简短描述（在本例中以正则表达式的形式）。只用于显示一次。
第二行定义开始状态，第三行是接受状态列表。
以下所有行都是转换规则。在此示例中，如果我们处于状态 "start" 并读取输入 'a'，则下一个状态为 "a"，如果我们读取其他任何内容，则为 "reject"。 （我知道我还没有实现“_”，意思是 else，如果读取未定义转换的输入，程序将崩溃。）

程序来了：

module FSM where

import System.IO

main :: IO ()
main = do
    putStr "Enter file name: "
    fileName <- getLine
    (description, startState, acceptingStates, stateTransitions) <- (readDef fileName)
    putStrLn ("FSM description: " ++ description)
    putStr "Enter FSM input: "
    input <- getLine
    let input = reverse input
    putStrLn "----------------"
    let (finalState, oldStates) = changeState input startState stateTransitions
    putStrLn (oldStates ++ finalState)
    checkAcception finalState acceptingStates

--reads the specified .fsm file and returns
--  the description of the FSM (first line),
--  the start state (second line),
--  the list of accepting states (third line),
--  and the list of tuples containing all states and transitions (remaining lines)
readDef :: String -> IO (String, String, [String], [(String, [(Char,String)])])
readDef fileName = do
    contents <- readFile (fileName ++ ".fsm")
    let lineList = lines contents
    let description = read (head lineList)
    let startState = read (lineList !! 1)
    let acceptingStates = read (lineList !! 2)
    let stateTransitions = read (filter (/='\t') (concat (drop 3 lineList)))
    return (description, startState, acceptingStates, stateTransitions)

--recursive function that takes the input, start state, and state transitions
--and computes the new state by a call to itself with the old state and a part of the input
changeState :: String -> String -> [(String, [(Char,String)])] -> (String, String)

changeState startState [] _ = (startState, "")

changeState startState (x:xs) stateTransitions = do
    let (currentState, oldStates) = changeState xs startState stateTransitions
    let newState = findKey x (findKey currentState stateTransitions)
    let oldStates = (oldStates ++ currentState ++ " -(" ++ [x] ++ ")-> ")
    return (newState, oldStates)

--helper function to find a key in a list of tuples and return the corresponding value
--(because we are not using the map notation in the .fsm file)
findKey :: (Eq k) => k -> [(k,v)] -> v
findKey key xs = snd . head . filter (\(k,v) -> key == k) $ xs

--checks for a given state whether or not it is in the list of accepting states
checkAcception :: String -> [String] -> IO ()
checkAcception finalState acceptingStates = do
    let accept = any (==finalState) acceptingStates
    if accept
        then putStrLn "Input accepted!!"
        else putStrLn "Input rejected!!"

想法是让用户选择一个从中加载定义的文件（readDef，效果很好）。然后系统会提示他输入一些 FSM 工作的输入。
递归 changeState 然后执行实际工作（效果不佳...）。
最后，显示状态和转换序列，并检查最终状态是否为接受状态 (checkAcceptance)。

现在，不要试图优化我写的东西。我知道，可以改进定义的建模方式，并且可以使用一些高阶 Haskell foo 将我写的许多行写得更短。但是请帮我解决上面列出的问题（当然还要帮我让它工作）。
非常感谢。

最后一件事：我正在为我大学的一个研讨会尝试一些 Haskell，所以如果软件架构组的某个人用 google 搜索我的代码并读到这个：嗨 :)

Answer 1

您只需将 changeState 函数的第二个子句更改为：

即可编译

changeState startState (x:xs) stateTransitions =
    let (currentState, oldStates) = changeState xs startState stateTransitions
        newState = findKey x (findKey currentState stateTransitions)
        oldStates2 = (oldStates ++ currentState ++ " -(" ++ [x] ++ ")-> ")
    in (newState, oldStates2)

我们 1) 删除了 do，2) 合并了 let 子句和 3) 重命名了第二次出现的 oldState 变量到 oldState2。在 Haskell 中，我们不重新定义变量——我们只是创建一个具有新名称的变量。完整代码可在此处获得：http://lpaste.net/118404

当你写：

(new, old) = changeState ...

你是说 changeState 是一个纯函数。如果你用 do ... return (...) 定义 changeState 你说它是一个单子计算，当你调用它时你需要在 do 块中使用箭头 <-：

(new, old) <- changeState ...

因为changeState是一个纯函数（不需要做IO）你还不如把它作为一个纯函数，所以没有理由使用do和return.

Answer 2

问题是 do 表示法和 return 函数并不像您认为的那样工作。在 Haskell 中：return 并不表示函数应该结束（尽管它最常见于函数的结尾）；它只是意味着参数应该包含在 Monad 中。因为应用了所有参数的函数类型是 (String,String) 编译器认为您正在尝试使用这样的东西：（没有 GHC 扩展实际上不会编译，如果使用会抛出异常，因为我使用 undefined)

instance Monad ((,) String) where
  (>>=) = undefined :: (String,a) -> (a -> (String,b)) -> (String,b)
  return = undefined :: a -> (String,a)

但是编译器已经知道 (String,String) -> (String,String) 与 a -> (String,a) 不匹配，所以它没有检查实例是否存在。解决这个问题揭示了另一个问题：你在同一个函数中定义了两次 oldStates，这在 Haskell 中不起作用，除非这两个定义在不同的范围内。

这是你的函数修改后可以正确编译，但我还没有测试它。

changeState :: String -> String -> [(String, [(Char,String)])] -> (String, String)

changeState startState [] _ = (startState, "")

changeState startState (x:xs) stateTransitions = let
    (currentState, oldStates) = changeState xs startState stateTransitions
    newState = findKey x (findKey currentState stateTransitions)
    oldStates' = (oldStates ++ currentState ++ " -(" ++ [x] ++ ")-> ")
    in (newState, oldStates')

递归函数中的类型匹配和 IO 问题

Trouble with type matching and IO in a recursive function

haskell

recursion

io

pattern-matching

type-mismatch