CODEWITHSUNDEEP
parsinghaskelllazy-evaluationghci
papagaga
papagaga

Reputation: 1158

is my parser lazy?

I'm playing with the functional pearl by Hutton and Meijer (https://www.cs.nott.ac.uk/~gmh/pearl.pdf). With the primitive functions defined in it, I've made a very basic csv parser:

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)

I was trying to get a sense of what was really evaluated when I call this parser. So in 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]]),[])]

So I see that the next parsing step is still a thunk (_t5). However the input stream is now: [] -so it seems to have been consumed entirely.

Where did it go? What shall I deduce from this? I'm wondering if my parser is lazy at all...

Edit: self-contained code as requested:

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)

Upvotes: 4

Views: 190

Answers (1)

Paul Johnson
Paul Johnson

Reputation: 17786

The problem may lie in your definition of "+++", which throws away all but the first parse. The "case" statement is strict; it forces the parse to find the first full parse of p +++ q, and if you do some more tracing you may find out that this has to scan to the end of the text in order to determine what a valid parse is. "sepBy" and "many" are likely to have this problem as they use "+++" to allow an empty parse.

Why don't you say "(+++) = mplus" ?

Upvotes: 1

Related Questions