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

Question

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

我必须处理 string 中的单个字符，否则解析器将只返回空列表。确切地说，如果我删除这一行 string [c] = do char c; return [c]它不会再工作了。我期待着 string (c:s)会处理 string (c:[])适本地。这里可能是什么原因？

在我看来，string定义应等同于 string s = mapM char s因为它会创建一个列表 [Parser Char]对于 s 中的每个字符并将结果收集为 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

附注。我认为问题的标题不够暗示，如果您有更好的想法，请提出编辑。

Answer 1

既然你做了 string [] = empty而不是 string [] = return [] ，您不能将其用作构建列表的递归的基本情况。

fmap f ma = f <$> ma错了，因为 <$>根据 fmap 定义.如果要定义 fmap就您的其他实例而言，然后执行 fmap = liftA或 fmap = liftM .自 mapM用途 fmap内部但你原来的string没有，这个问题在你的第一个简单测试中没有出现。