我的解析器是懒惰的吗？

Question

我在玩 Hutton 和 Meijer (https://www.cs.nott.ac.uk/~gmh/pearl.pdf) 的功能珍珠。通过其中定义的原始函数，我制作了一个非常基本的 csv 解析器：

csvFile :: Parser [[String]]
csvFile = record `sepBy` char '\n'

record :: Parser [String]
record = (quotedField +++ unquotedField) `sepBy` char ';'

unquotedField :: Parser String
unquotedField = many (sat (not . (`elem` ";\n")))

quotedField :: Parser String
quotedField = do
    char '"'
    xs <- many (sat (not . (== '"')))
    char '"'
    ys <- do { zs <- quotedField; return ('"':zs) } +++ return []
    return (xs++ys)

当我调用这个解析器时，我试图了解真正评估的是什么。所以在 GHCI 中：

*Main> let tst = "123;123;123\n123;\"123;123\";124\n124;122;125"
*Main> let psd = parse csvFile tst
*Main> let x = head . fst . head $ psd
*Main> x
["123","123","123"]
*Main> :p psd
psd = [(["123","123","123"] : (_t5::[[String]]),[])]

所以我看到下一个解析步骤仍然是一个thunk (_t5)。但是输入流现在是：[] - 所以它似乎已经被完全消耗掉了。

它去哪儿了？我应该从中推断出什么？我想知道我的解析器是不是很懒惰...

编辑：要求的独立代码：

import Control.Monad
import Data.Char

newtype Parser a = Parser (String -> [(a, String)])

parse :: (Parser a) -> (String -> [(a, String)])
parse (Parser p) = p

instance Monad Parser where
     return a = Parser (\cs -> [(a, cs)])
     p >>= f  = Parser (\cs -> concat [parse (f a) cs' | (a, cs') <- parse p cs])

instance MonadPlus Parser where
    mzero = Parser(\cs -> [])
    mplus p q = Parser (\cs -> (parse p cs) ++ (parse q cs))

(+++) :: Parser a -> Parser a -> Parser a 
p +++ q = Parser (\cs -> case (parse (p `mplus` q) cs) of
                                [] -> []
                                (x:xs) -> [x])

item :: Parser Char
item = Parser (\cs -> case cs of 
                        (c:nc) -> [(c, nc)]
                        _ -> [])

sat :: (Char -> Bool) -> Parser Char
sat f = do { c <- item ; if f c then return c else mzero }

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

many :: Parser a -> Parser [a]
many p = many1 p +++ (return [])

many1 :: Parser a -> Parser [a]
many1 p = do {t <- p; ts <- many p; return (t:ts) }

sepBy :: Parser a -> Parser b -> Parser [a]
p `sepBy` sep = sepBy1 p sep +++ do {x <- p; return [x]} 

sepBy1 :: Parser a -> Parser b -> Parser [a]
p `sepBy1` sep = do { x <- p; sep; xs <- p `sepBy` sep; return (x:xs)}

csvFile :: Parser [[String]]
csvFile = record `sepBy` char '\n'

record :: Parser [String]
record = (quotedField +++ unquotedField) `sepBy` char ';'

unquotedField :: Parser String
unquotedField = many (sat (not . (`elem` ";\n")))

quotedField :: Parser String
quotedField = do
    char '"'
    xs <- many (sat (not . (== '"')))
    char '"'
    ys <- do { zs <- quotedField; return ('"':zs) } +++ return []
    return (xs++ys)

Answer 1

问题可能出在你对“+++”的定义上，它除了第一个解析外，其他的都丢掉了。 "case" 语句是严格的；它强制解析找到 p+++ q 的第一个完整解析，如果你做更多的跟踪，你可能会发现这必须扫描到文本的末尾才能确定什么是有效的解析。 "sepBy" 和 "many" 可能有这个问题，因为他们使用 "+++" 来允许空解析。

你为什么不说“(+++) = mplus”？

我的解析器是懒惰的吗？

is my parser lazy?

parsing

haskell

lazy-evaluation

ghci