Unable to define a parser in Haskell: Not in scope: type variable ‘a’-CodePudding

I am trying to define a parser in Haskell. I am a total beginner and somehow didn't manage to find any solution to my problem at all.

For the first steps I tried to follow the instructions on the slides of a powerpoint presentation. But I constantly get the error "Not in scope: type variable ‘a’":

type Parser b = a -> [(b,a)]
item :: Parser Char
item = \inp -> case inp of
 [] -> []
 (x:xs) -> [(x:xs)]

error: Not in scope: type variable ‘a’
   |
11 | type Parser b = a -> [(b,a)]
   |                          ^

I don't understand the error but moreover I don't understand the first line of the code as well:

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

What is this supposed to do? On the slide it just tells me that in Haskell, Parsers can be defined as functions. But that doesn't look like a function definition to me. What is "type" doing here? If it s used to specify the type, why not use "::" like in second line above? And "Parser" seems to be a data type (because we can use it in the type definition of "item"). But that doesn't make sense either.

The line derives from:

type Parser = String -> (String, Tree)

The line I used in my code snippet above is supposed to be a generalization of that.

Your help would be much appreciated. And please bear in mind that I hardly know anything about Haskell, when you write an answer :D

CodePudding user response：

There is a significant difference between the type alias type T = SomeType and the type annotation t :: SomeType.

type T = Int simply states that T is just another name for the type Int. From now on, every time we use T, it will be replaced with Int by the compiler.

By contrast, t :: Int indicates that t is some value of type Int. The exact value is to be specified by an equation like t = 42.

These two concepts are very different. On one hand we have equations like T = Int and t = 42, and we can replace either side with the other side, replacing type with types and values with values. On the other hand, the annotation t :: Int states that a value has a given type, not that the value and the type are the same thing (which is nonsensical: 42 and Int have a completely different nature, a value and a type).

type Parser = String -> (String, Tree)

This correctly defines a type alias. We can make it parametric by adding a parameter:

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

In doing so, we can not use variables in the right hand side that are not parameters, for the same reason we can not allow code like

f x = x   y   -- error: y is not in scope

Hence you need to use the above Parser type, or some variation like

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

By contrast, writing

type Parser a = b -> [(b, a)]  -- error

would use an undeclared type b, and is an error. At best, we could have

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

which compiles. I wonder, though, is you really need to make the String type even more general than it is.

So, going back to the previous case, a possible way to make your code run is:

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

item :: Parser Char
item = \inp -> case inp of
 [] -> []
 (x:xs) -> [(x, xs)]

Note how [(x, xs)] is indeed of type [(Char, String)], as needed.

If you really want to generalize String as well, you need to write:

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

item :: Parser Char String
item = \inp -> case inp of
 [] -> []
 (x:xs) -> [(xs, x)]