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

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 :

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 :

...

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@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners