[Haskell-cafe] Re: Parsers are monadic?

[Claus Reinke]

>> First post. I'm a newbie, been using Haskell for about a
>> week and love it. Anyway, this is something I don't
>> understand. Parsers are monadic. I can see this if the
>> parser is reading from an input stream but if there's just a
>> block of text can't you just have the parser call itself
>> recursively feeding the unparsed text down the recursion and
>> tacking nodes onto the tree as the recursions return,
>> finally returning the whole tree to the top level
>> caller. Seems this meets the criteria for pure
>> functionality, same result every time with same args.
>> myParser :: [Char] -> ParseTree
> 
> Looks as if others may be answering questions you didn't ask.  

or asking and answering other questions related to the subject?-)

but if the original question hasn't been answered yet, 
consider two of the statements in that paragraph:

- "feeding the unparsed text down the recursion"
- "tacking nodes onto the tree as the recursions return"

that is a description in terms of modifications (taking
remainders of the input, adding nodes to the output).

functionally, you'd just want to define the output in
terms of the input, which works fine if you can tell
in advance which parts of the input determine which 
parts of the output:

    parseInt intString = foldl (\n d->d+10*n) 0 
        $ map parseDigit intString

    parseDigit char | char `elem` "0123456789" = 
        digitToInt char

things get more interesting if you want to define a complex 
parser AB in terms of parsers A and B for parts of the 
input, and the only way of finding out what "the unparsed 
text" is that should be fed to parser B is to run parser A.

now, parser A has to return its part of the tree as well as
"the unparsed text", and the combined parser has to feed 
the leftover text from A into B. you don't have to do that
monadically, but the type 'Parser =  String -> (Tree,String)' 
is one functional way of arranging things that happens to
fit the description of a state transformer monad..

claus