Idris parser combinator GADT

2
votes

I am currently working on implementing a simple parser combinator library in Idris to learn the language and better understand type systems in general, but am having some trouble wrapping my head around how GADTs are declared and used. The parser data type that I am trying to formulate looks like (in Haskell): type Parser a = String -> [(a,String)], from this paper. Basically, the type is a function that takes a string and returns a list.

In Idris I have:

data Parser : Type -> Type where
    fail : a -> (String -> [])
    pass : a -> (String -> [(a,String)])

where the fail instance is a parser that always fails (i.e.- will be a function that always returns the empty list) and the pass instance is a parser that consumed some symbol. When loading the above into the interpreter, I get an error that there is a type mismatch between List elem and the expected type Type. But when I check the returned type of the parser in the repl with :t String -> List Type I get Type, which looks like it should work.

I would be very grateful if anyone could give a good explanation of why this data declaration does not work, or a better alternative to representing the parser data type.

2
parsingtypesgadtidris

2 Answers

2
votes

In defining your datatype Parser, the first line is saying this type takes a type and returns a type, in this case it takes an a and returns a Parser a.

So, your constructors should return Parser a.

Similar to a List which takes an a and returns a List a.

What you are currently returning in your constructors are not of type Parser - easily seen as nowhere does the word Parser occur on the right hand side.

Beyond that though, I'm not sure how you would best represent this. However, there are some parser libraries already written in Idris, looking at these might help ? For example, have a look at this list of libraries, parsers are the first ones mentioned :- Idris libraries

2
votes

In Haskell, 

type Parser a = String -> [(a,String)]

doesn't create a new type, it is merely a type synonym. You can do something similar in Idris as

Parser : Type -> Type
Parser a = String -> List (a, String)

and then define your helper definitions as simple functions that return Parser as:

fail : Parser a
fail = const []

pass : a -> Parser a
pass x = \s => [(x, s)]