applicative functor: <*> and partial application, how it works

Viewed 543

I am reading the book Programming in Haskell by Graham Hutton and I have some problem to understand how <*> and partial application can be used to parse a string.

I know that pure (+1) <*> Just 2 produces Just 3 because pure (+1) produces Just (+1) and then Just (+1) <*> Just 2 produces Just (2+1) and then Just 3

But in more complex case like this:

-- Define a new type containing a parser function
newtype Parser a = P (String -> [(a,String)])

-- This function apply the parser p on inp
parse :: Parser a -> String -> [(a,String)]
parse (P p) inp = p inp

-- A parser which return a tuple with the first char and the remaining string
item :: Parser Char
item = P (\inp -> case inp of
    []     -> []
    (x:xs) -> [(x,xs)])

-- A parser is a functor
instance Functor Parser where
  fmap g p = P (\inp -> case parse p inp of
    []              -> []
    [(v, out)]      -> [(g v, out)])

-- A parser is also an applicative functor
instance Applicative Parser where
  pure v = P (\inp -> [(v, inp)])
  pg <*> px = P (\inp -> case parse pg inp of
    []              -> []
    [(g, out)]      -> parse (fmap g px) out)

So, when I do:

parse (pure (\x y -> (x,y)) <*> item <*> item) "abc"

The answer is:

[(('a','b'),"c")]

But I don't understand what exactly happens. First:

pure (\x y -> (x,y)) => P (\inp1 -> [(\x y -> (x,y), inp1)])

I have now a parser with one parameter.

Then:

P (\inp1 -> [(\x y -> (x,y), inp1)]) <*> item 
=> P (\inp2 -> case parse (\inp1 -> [(\x y -> (x,y), inp1)]) inp2 of ??? 

I really don't understand what happens here. Can someone explain, step by step, what's happens now until the end please.

6 Answers
Related