[Haskell-beginners] Applicative: how <*> really works

[Ivan Llopard]

Hi Yassine,

I prefer to explain you with an abstract view of these definitions.
Unrolling this stuff in your mind (or paper) can be complex and, IMO, it
might be useless as it does not give you any specific hints to build even
more complex ones.

You can view Parser a as an object with a certain structure (or form, or
definition if you prefer). However, you do not want to know how complex its
structure or definition is. You are certain about one thing, it holds some
value of type a.
Let's say that such value is "hidden" by Parser. The same idea applies to
Maybe a.

Then, you want to work with that value no matter the structure of Parser.
As you already know, fmap allows you to do that. You can go from Parser a
to Parser b with a function from a to b.
The applicative allows you to go further. If you have a hidden function
(e.g. Parser (a->b)) and a hidden parameter (Parser a). Then you want to
apply that hidden function to the hidden parameter in order to obtain a
Parser b.
That is what the expression parserF <*> ParserA would do if parserF hides a
function and parserA its parameter.

Now, you need to know more about the meaning of Parser a. It is an object
that reads the input and produce a result (or token) accordingly.
The returned value of the parser is a list of (result, remaining_input).
The interesting part is the result value, which is of type a. You want to
play around with it. Again, fmap is an easy way. Going from Parser a to
Parser b via fmap does not change the parsing action of Parser a, you will
have a Parser b but the behavior remains the same. You just played with the
result of the first parser.

The functor instance tells that more precisely (fixed):

instance Functor Parser where
fmap g (P p) = P (\inp -> case p inp of
[]              -> []
 [(v, out)]      -> [(g v, out)])

Now look at the definition of the applicative

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)

First of all, the function "parser" applies the parser, i.e., it parses the
input and returns the list [(g, out)]. Here, we have two applications of
"parser".
The first one applies parser pg, "case parse pg inp". Obviously, pg hides a
function "g".
Now you preserve the same behavior of px but you fmap on it function "g".
That is, the parser "fmap g px" will do the same as px but its result is
changed by g.
And finally, you apply such parser.

Let us take the first two terms of your example

first_item = pure (\x y -> (x,y)) <*> item

then g = \x y -> (x,y)
which is a higher order function. In the expression, g is applied partially
over the result of item. You know that item returns the first char of the
input, 'a'.
first_item is then a parser that hides a function of the form h = \y ->
('a', y).

Because it hides a function, you can use the applicative again

first_term <*> item

and h will be applied to the result of item again. Because we already
applied item once, the remaining input is "bc". Then, item will give you
'b' as a result.
Now h 'b' = ('a, 'b'), which is the result of your final parser plus the
remaining input "c". Applying the final parser, you obtain

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

I hope this will help you !

Best,
Ivan

2017-08-03 21:19 GMT+02:00 Yassine <yassine912 at gmail.com>:

> Hi,
>
> I have a question about functor applicate.
>
> I know that:
> pure (+1) <*> Just 2
>
>
> produce: Just 3
> because pure (+1) produce Just (+1) and then Just (+1) <*> Just 2
> produce Just (2+1)
>
>
> but in more complex case like:
> newtype Parser a = P (String -> [(a,String)])
>
> parse :: Parser a -> String -> [(a,String)]
> parse (P p) inp = p inp
>
>
> item :: Parser Char
> item = P (\inp -> case inp of
>  []     -> []
> (x:xs) -> [(x,xs)])
>
> instance Functor Parser where
> fmap g p = P (\inp -> case p inp of
> []              -> []
>  [(v, out)]      -> [(g v, out)])
>
> 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)
>
>
> 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 (\inp -> [(\x y -> (x,y), inp)])
>
> Then:
> P (\inp -> [(\x y -> (x,y), inp)]) <*> item => ???
>
> Can someone explain what's happens step by step please.
>
> Thank you.
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20170804/c738b376/attachment.html>