Recursive Parser in Haskell

Question

I'm writing a parser in Haskell, and one of the parsing functions (prefixParser) should return a modified version of itself on every call. The code here is simplified, but I hope every necessary bit of information is included.

type MyParsec r = Parsec [Char] () Identity r
newtype SomeResult = String
newtype RecursiveParser = MyParsec (SomeResult, RecursiveParser)
items :: RecursiveParser -> MyParsec [SomeResult]
items prefixParser = do
 (someResult, newPrefixParser) <- prefixParser
 rst <- items newPrefixParser
 return (someResult : rst)

Now the trouble is that prefixParser's type is RecursiveParser but I call it inside a do block that expects a MyParsec. Ergo I get a

Couldn't match expected type

error. Can I even do something like this or am I (as usual) not quite getting Haskell's type system?

(The prefixParser is meant to parse an incrementing number [1. 2. 3. ...], and as of yet not implemented.)

• Li-yao Xia: use type instead of newtype
• luqui: You are not using newtype correctly. It's worth reading about newtype (and its big brother data)
• chi: @Li-yaoXia We can't use type recursively. He needs to use a newtype, but in the correct way.

Answer 1

This is wrong:

newtype RecursiveParser = MyParsec (SomeResult, RecursiveParser)

Above, MyParsec is the name of a new data constructor, which is completely unrelated to the MyParser type constructor. Essentially, the above definition defines RecursiveParser to be a pair (SomeResult, RecursiveParser), wrapped under the new constructor MyParsec.

Recall the newtype syntax is

newtype NewtypeName = NewConstructorName SomeType

To actually use the MyParsec (...) type, you need to specify the name of the constructor as follows. It is customary to name it using the same name as the newtype itself.

newtype RecursiveParser = RecursiveParser (MyParsec (SomeResult, RecursiveParser))

Then, you can adapt your code so to remove the wrapper data constructor.

items :: RecursiveParser -> MyParsec [SomeResult]
items (RecursiveParser prefixParser) = do
 (someResult, newPrefixParser) <- prefixParser
 rst <- items newPrefixParser
 return (someResult : rst)

• John Smith: so it basically was a syntactical error on my part, oh my dear... thank you!