FParsec parse unordered clauses

Question

I want to parse some grammar like the following

OUTPUT data
GROUPBY key
TO location
USING object

the order of the GROUPBY TO USING clauses is allowed to vary, but each clause can occur at most once.

Is there a convenient or built-in way to parse this in FParsec? I read some questions and answers that mentions Haskell Parsec permute. There doesn't seem to be a permute in FParsec. If this is the way to go, what would I go about building a permute in FParsec?

Answer 1

I don't think there's a permutation parser in FParsec. I see a few directions you could take it though.

• In general, what @FuleSnabel suggests is pretty sound, and probably simplest to implement. Don't make the parser responsible for asserting the property that each clause appears at most once. Instead parse each clause separately, allowing for duplicates, then inspect the resulting AST and error out if your property doesn't hold.

• You could generate all permutations of your parsers and combine them with choice. Obviously this approach doesn't scale, but for three parsers I'd say it's fair game.

• You could write your own primitive for parsing using a collection of parsers applied in any order. This would be a variant of many where in each step you make a choice of a parser, then discard that parser. So in each step you choose from a shrinking list of parsers until you can't parse anymore, finally returning the results collected along the way.

• You could use user state to keep track of parsers already used and fail if a parser would be used twice within the same context. Not sure if this would yield a particularly nice solution - haven't really tried it before.