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

Ivan Llopard ivanllopard at gmail.com
Thu Aug 17 19:20:10 UTC 2017


Exactly, It is left-associative and it will apply "pure g", which does
nothing in terms of parsing but put g into the parsing result, and then
apply item.

Another way to think about it, is to forget about the list and think only
in terms of types.
With a value of type Parser (a -> (b, c)) and Parser a you can use <*> to
get a value of type Parser (b, c).
Then, if you execute such a parser you will have a list of nested tuples as
you requested, i.e. [(b, c), String].

Try your first example with g = (\x -> (x,0)) and pure g <*> item. Play
with different expressions and the applicative operator.

Best,
Ivan

2017-08-05 0:29 GMT+02:00 Yassine <yassine912 at gmail.com>:

> 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
> >
> _______________________________________________
> 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/20170817/5e0e9d57/attachment-0001.html>


More information about the Beginners mailing list