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

[Yassine]

Thanks for you nice answer but I still have some difficulties.

When you do:
g = (\x y -> (x,y))
first_item = pure g <*> item

Because <*> is left associative, we do first the application of g on
item before apply item, is it correct ?

Furthermore, item return a list containing a tuple with the first
character and the remaining of the string. So how can I get a list
with a tuple containing another tuple with the parsed characters
(inner tuple) and the remaining of the string (in the outer tuple).

2017-08-04 23:30 GMT+02:00 Ivan Llopard <ivanllopard at gmail.com>:
> 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
>
>
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>