1

From Brent Yorgey's 2013 Penn class, after getting help on defining a Functor Parser, I'm attempting to make an Applicative Parser:

--p1 <*> p2 represents the parser which first runs p1 (which will
--consume some input and produce a function), then passes the
--remaining input to p2 (which consumes more input and produces
--some value), then returns the result of applying the function to the
--value

Here's my attempt:

instance Applicative (Parser) where
  pure x                    = Parser $ \_ -> Just (x, [])
  (Parser f) <*> (Parser g) = case (\ys -> f ys) of Nothing      -> Parser Nothing
                                                    Just (_, xs) -> Parser $ g xs

However, I'm getting compile-time errors on the apply (<*>) definition.

Intuitively, I believe that using <*> achieves AND functionality.

If I have a parser for foo and a parser for bar, then I should be able to use apply <*> to say: foo followed by bar. In other words, input of foobar should successfully match, whereas foobip would not. It would fail on the second parser.

However, I believe that the types are:

Parser (a -> b) -> Parser a -> Parser b

So, that makes me think that my intuition is not entirely correct.

Please give me a tip to guide me towards understanding how to implement apply.

2
  • Here's a leading question: if p1 "will consume some input and produce a function" and you need "the result of applying the function", where in your code can you find that function? Where can you find its application?
    – rampion
    Dec 30, 2014 at 3:49
  • 1
    Your types are right. You need Parser b, so you should return something of the same form as pure x; you should write Parser $ \s -> at the start. Because Parser f :: Parser (a->b) You have f:: String -> Maybe (a->b,String), so you can apply f to a string to get a Maybe (a->b,String) which you can pattern match on. If that's Just (someFunction,remainingInput) then you could apply g to the remainingInput to get something of type Maybe (a,String), and if you get a result from that like Just (aValue,finalRemainingInput) you could apply someFunction to aValue.
    – AndrewC
    Dec 30, 2014 at 9:48

1 Answer 1

7

Your code is predicated on a misunderstanding of what a Parser is. Don't worry, virtually everybody makes this mistake.

newtype Parser a = Parser { runParser :: String -> Maybe (a, String) }

Lets break down what this means.

String -> Maybe (a, String)
[1]       [2]   [3] [4]

[1]: I take a string and return Maybe (a, String)

[2]: I might not succeed in parsing the input into the desired datatype

[3]: The desired type I am parsing the String into

[4]: Remaining input after having consumed the amount of data required to parse a

Parser is a function of text input to Maybe a tuple of a value and the rest of the text. Parser is emphatically not a tuple, otherwise you wouldn't have a parser. Just data in a tuple.

I'm not going to tell you how to implement <*> and nobody else should either as it would deprive you of the experience.

However, I'll give you pure so you understand the basic pattern:

 pure a = Parser (\s -> Just (a, s))

See? It's a function of s -> Maybe (a, s). I intentionally mimicked the type variables in my terms to make it more obvious.

1
  • ...and the key difference with this definition of pure is that the input it is given (s) is the same as the remaining input it returns, so it leaves the input stream alone rather than terminating the parse run by throwing away the rest of the input (_) and returning [] as the remaining input.
    – AndrewC
    Dec 30, 2014 at 8:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.