Problems with Haskell's Parsec <|> operator

Question

I am new to both Haskell and Parsec. In an effort to learn more about the language and that library in particular I am trying to create a parser that can parse Lua saved variable files. In these files variables can take the following forms:

varname = value

varname = {value, value,...}

varname = {{value, value},{value,value,...}}

I've created parsers for each of these types but when I string them together with the choice <|> operator I get a type error.

Couldn't match expected type `[Char]' against inferred type `Char'
  Expected type: GenParser Char st [[[Char]]]
  Inferred type: GenParser Char st [[Char]]
In the first argument of `try', namely `lList'
In the first argument of `(<|>)', namely `try lList'

My assumption is (although I can't find it in the documentation) that each parser passed to the choice operator must return the same type. Here's the code in question:

data Variable = LuaString ([Char], [Char])
          | LuaList ([Char], [[Char]])
          | NestedLuaList ([Char], [[[Char]]])
          deriving (Show)

main:: IO()
main = do
       case (parse varName "" "variable = {{1234,\"Josh\"},{123,222}}") of
            Left err -> print err
            Right xs -> print xs 

varName :: GenParser Char st Variable
varName = do{
        vName <- (many letter);
        eq <- string " = ";
        vCon <- try nestList
             <|> try lList 
             <|> varContent;
        return (vName, vCon)}

varContent :: GenParser Char st [Char]
varContent =  quotedString 
    <|> many1 letter
    <|> many1 digit

quotedString :: GenParser Char st [Char]
quotedString = do{
         s1 <- string "\""; 
         s2 <- varContent;
         s3 <- string "\"";
         return (s1++s2++s3)}

lList :: GenParser Char st [[Char]]
lList = between (string "{") (string "}") (sepBy varContent (string ","))

nestList :: GenParser Char st [[[Char]]]
nestList = between (string "{") (string "}") (sepBy lList (string ","))

Answer 1

That's correct.

(<|>) :: (Alternative f) => f a -> f a -> f a

Notice how both arguments are exactly the same type.

I don't exactly understand your Variable data type. This is the way I would do it:

data LuaValue = LuaString String | LuaList [LuaValue]
data Binding = Binding String LuaValue

This allows values to be arbitrarily nested, not just nested two levels deep like yours has. Then write:

luaValue :: GenParser Char st LuaValue
luaValue = (LuaString <$> identifier)
       <|> (LuaList <$> between (string "{") (string "}") (sepBy (string ",") luaValue))

This is the parser for luaValue. Then you just need to write:

binding :: GenParser Char st Binding
content :: GenParser Char st [Binding]

And you'll have it. Using a data type that accurately represents what is possible is important.

Answer 2

Indeed, parsers passed to the choice operator must have equal types. You can tell by the type of the choice operator:

(<|>) :: GenParser tok st a -> GenParser tok st a -> GenParser tok st a

This says that it will happily combine two parsers as long as their token types, state types and result types are the same.

So how do we make sure those parsers you're trying to combine have the same result type? Well, you already have a datatype Variable that captures the different forms of variables that can appear in Lua, so what we need to do is not return String, [String] or [[String]] but just Variables.

But when we try that we run into a problem. We can't let nestList etc. return Variables yet because the constructors of Variable require variable names and we don't know those yet at that point. There are workarounds for this (such as return a function String -> Variable that still expects that variable name) but there is a better solution: separate the variable name from the different kinds of values that a variable can have.

data Variable = Variable String Value
  deriving Show

data Value = LuaString String
           | LuaList [Value]
           deriving (Show)

Note that I've removed the NestedLuaList constructor. I've changed LuaList to accept a list of Values rather than Strings, so a nested list can now be expressed as a LuaList of LuaLists. This allows lists to be nested arbitrarily deep rather than just two levels as in your example. I don't know if this is allowed in Lua but it made writing the parsers easier. :-)

Now we can let lList and nestList return Values:

lList :: GenParser Char st Value
lList = do
  ss <- between (string "{") (string "}") (sepBy varContent (string ","))
  return (LuaList (map LuaString ss))

nestList :: GenParser Char st Value
nestList = do
  vs <- between (string "{") (string "}") (sepBy lList (string ","))
  return (LuaList vs)

And varName, which I've renamed variable here, now returns a Variable:

variable :: GenParser Char st Variable
variable = do
  vName <- (many letter)
  eq <- string " = "
  vCon <- try nestList
       <|> try lList 
       <|> (do v <- varContent; return (LuaString v))
  return (Variable vName vCon)

I think you'll find that when you run your parser on some input there are still some problems, but you're already a lot closer to the solution now than before.

I hope this helps!