How to parse unordered syntax

user_490815 0
Viewed 186
newtype Program = Program [Global] [Function]

I am parsing a source file with C-like syntax in Haskell, where global variables and functions are present at top level. It's straightforward to parse if they must come in order, say, functions after all global variables. But they can come in any order as shown below. How to handle syntax like this?

global0

function0

global1

function1

function2

global2

Seems sth like Parsec.Perm can be used, but the example works when all choices return the same type (decimal), where as my case returns either Global or Function.

parsec haskell
1 Answers

You don't need a permutation parser. Simple old many is fine. You can use Either to temporarily make them the same type, then partitionEithers to split them back out.

uncurry Program . partitionEithers
    <$> many (  (Left  <$> parseGlobal)
            <|> (Right <$> parseFunction)
             )

Edit: alternately, you could make them all be Programs and then combine them. Something like

instance Monoid Program where mempty = Program [] []
instance Semigroup Program where
    Program gs fs <> Program gs' fs' = Program (gs <> gs') (fs <> fs')

global x = Program [x] []
function x = Program [] [x]

and then use:

fold <$> many ((global <$> parseGlobal) <|> (function <$> parseFunction))

Very similar program structure, but maybe one or the other is more aesthetically appealing to you.

user_7916040
Related