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
– luqui, Commented Dec 23, 2019 at 10:11
@Li-yaoXia We can't use type recursively. He needs to use a newtype, but in the correct way. — chi
– chi, Commented Dec 23, 2019 at 10:34

chi · Accepted Answer · 2019-12-23 10:36:15Z

2

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)

edited Dec 23, 2019 at 10:36

answered Dec 23, 2019 at 10:27

chi

117k4 gold badges143 silver badges230 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

John Smith Over a year ago

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

Collectives™ on Stack Overflow

Recursive Parser in Haskell

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related