Creating recursive attoparsec parsers

Question

I encoded the attoparsec parser and ended up in a template where I want to turn parsers into recursive parsers (recursively merging them with the monad bind → = operator).

So, I created a function to turn the parser into a recursive parser as follows:

recursiveParser :: (a -> A.Parser a) -> a -> A.Parser a recursiveParser parser a = (parser a >>= recursiveParser parser) <|> return a 

This is useful if you have a recursive data type like

 data Expression = ConsExpr Expression Expression | EmptyExpr parseRHS :: Expression -> Parser Expression parseRHS e = ConsExpr e <$> parseFoo parseExpression :: Parser Expression parseExpression = parseLHS >>= recursiveParser parseRHS where parseLHS = parseRHS EmptyExpr 

Is there a more idiomatic solution? It seems that recursiveParser should be some kind of fold ... I also saw sepBy in the docs, but this method seems to work better for my application.

EDIT: Oh, actually now that I think about it, there really should be something like fix ... I don’t know how I forgot about it.

EDIT2: Rotsor is great for its alternative for my example, but I'm afraid that my AST is actually a bit more complicated. In fact, it looks something like this (although it is still simplified)

 data Segment = Choice1 Expression | Choice2 Expression data Expression = ConsExpr Segment Expression | Token String | EmptyExpr 

where the string a -> b brackets to the right and c:d brackets to the left, c : binding is more tight than -> .

those. a -> b evaluates to

 (ConsExpr (Choice1 (Token "a")) (Token "b")) 

and c:d evaluates to

 (ConsExpr (Choice2 (Token "d")) (Token "c")) 

I suppose I could use foldl for one and foldr for the other, but there is even more complexity. Note that it is recursive in a slightly strange way, so "a:b:c -> e:f -> :g:h ->" is actually a valid string, but "-> a" and "b:" - no. At the end of fix it seemed easier to me. I renamed the recursive method as follows:

 fixParser :: (a -> A.Parser a) -> a -> A.Parser a fixParser parser a = (parser a >>= fixParser parser) <|> pure a 

Thanks.

Answer 1

Why not just parse the list and collapse it at all costs? Maybe something is missing for me, but it looks more natural to me:

 consChain :: [Expression] -> Expression consChain = foldl ConsExpr EmptyExpr parseExpression :: Parser Expression parseExpression = consChain <$> many1 parseFoo 

And this is also shorter.

As you can see, consChain now independent of parsing and may be useful elsewhere. In addition, if you separate the folding of the result, in this case, a somewhat unintuitive recursive parsing will simplify to many or many1 .

You can take a look at how many also implemented:

 many :: (Alternative f) => fa -> f [a] many v = many_v where many_v = some_v <|> pure [] some_v = (:) <$> v <*> many_v 

It has a lot to do with your recursiveParser :

• some_v is similar to parser a >>= recursiveParser parser
• many_v is similar to recursiveParser parser

You may ask why I called your recursive parser function non-intuitive. This is due to the fact that this template allows the parser argument to influence the parsing behavior ( a -> A.Parser a , remember?), Which may be useful, but not obvious (I don’t see a use case yet). The fact that your example does not use this function makes it redundant.