Monadic Parser - 处理一个字符的字符串

Question

我正在阅读这篇 Monadic Parsing 文章，同时我正在尝试在 Haskell 中实现一个非常简单的字符串解析器并更好地理解使用 monad。在下面你可以看到我的代码，实现了匹配单个字符或整个字符串的功能。它按预期工作，但我观察到两个我无法解释的奇怪行为。

我必须处理 string 中的单个字符，否则解析器将 return 只有空列表。确切地说，如果我删除这一行 string [c] = do char c; return [c] 它将不再起作用。我原以为 string (c:s) 会正确处理 string (c:[])。这可能是什么原因？
在我看来，string 定义应该等同于 string s = mapM char s，因为它将为 s 中的每个字符创建一个 [Parser Char] 列表并将结果收集为 Parser [Char]。如果我使用基于 mapM 的定义，程序将陷入无限循环并且不会打印任何内容。我在这里想念有关惰性评估的内容吗？

.

module Main where

newtype Parser a = Parser { apply :: String->[(a, String)] }

instance Monad Parser where
    return a = Parser $ \s -> [(a, s)]
    ma >>= k = Parser $ \s -> concat [apply (k a) s' | (a, s') <- apply ma s]

instance Applicative Parser where
    pure = return
    mf <*> ma = do { f <- mf; f <$> ma; }

instance Functor Parser where
    fmap f ma = f <$> ma

empty :: Parser a
empty = Parser $ const []

anychar :: Parser Char
anychar = Parser f where
    f [] = []
    f (c:s) = [(c, s)]

satisfy :: (Char -> Bool) -> Parser Char
satisfy prop = do
    c <- anychar
    if prop c then return c
    else empty

char :: Char -> Parser Char
char c = satisfy (== c)

string :: String -> Parser String
string [] = empty
string [c] = do char c; return [c] --- if I remove this line, all results will be []
string (c:s) = do char c; string s; return (c:s)

main = do
    let s = "12345"
    print $ apply (string "123") s
    print $ apply (string "12") s
    print $ apply (string "1") s
    print $ apply (string []) s

PS。我认为问题的标题不够具有启发性，如果您有更好的想法，请提出修改。

Answer 1

string [] = empty

意思是：“如果你需要解析一个空字符串，失败——它根本无法被解析，无论输入字符串是什么”。

相比之下，

string [] = return ""

意思是：“如果你需要解析一个空字符串，成功并且 return 空字符串——它总是可以被解析，不管输入字符串是什么”。

通过使用第一个等式，当您在 string (c:cs) 的情况下递归时，您需要在一个字符 (string [c]) 处停止，因为达到零个字符将运行 empty 并使整个解析器失败。

因此，您需要使用 string [c] = return [c] 等式，或者修改基本的“空字符串”情况，使其成功。可以说，后者会更自然。

Answer 2

由于您使用的是 string [] = empty 而不是 string [] = return []，因此您不能将其用作构建列表的递归的基本情况。
fmap f ma = f <$> ma 是错误的，因为 <$> 是根据 fmap 定义的。如果您想根据其他实例定义 fmap，请执行 fmap = liftA 或 fmap = liftM。由于 mapM 在内部使用 fmap 而你原来的 string 没有，所以这个问题在你的第一个简单测试中没有出现。

Monadic Parser - 处理一个字符的字符串

Monadic Parser - handling string with one character

monads

haskell