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.)

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

chi chi · Accepted Answer · 2019-12-23T10:27:49

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)

Recursive Parser in Haskell

1 Answers