Applicative: how <*> really works

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Applicative: how <*> really works

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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Applicative: how <*> really works

David McBride
This is a bit complicated for this list.  You might have a bit more
luck posting this to stackoverflow.com.

On Thu, Aug 3, 2017 at 3:19 PM, Yassine <[hidden email]> wrote:

> 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
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Applicative: how <*> really works

Yassine
Ok, thanks for your answer

2017-08-04 20:04 GMT+02:00 David McBride <[hidden email]>:

> This is a bit complicated for this list.  You might have a bit more
> luck posting this to stackoverflow.com.
>
> On Thu, Aug 3, 2017 at 3:19 PM, Yassine <[hidden email]> wrote:
>> 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
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Applicative: how <*> really works

Jeffrey Brown
If you post there, you could put the link on this thread; I'd be interested.

On Fri, Aug 4, 2017 at 3:04 PM, Yassine <[hidden email]> wrote:
Ok, thanks for your answer

2017-08-04 20:04 GMT+02:00 David McBride <[hidden email]>:
> This is a bit complicated for this list.  You might have a bit more
> luck posting this to stackoverflow.com.
>
> On Thu, Aug 3, 2017 at 3:19 PM, Yassine <[hidden email]> wrote:
>> 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
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners



--
Jeff Brown | Jeffrey Benjamin Brown
Website   |   Facebook   |   LinkedIn(spammy, so I often miss messages here)   |   Github   

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Applicative: how <*> really works

sasa bogicevic
Hey does this even compile for you ?

I get this in the Functor instance for Parser

     • Couldn't match expected type ‘String -> [(a, String)]’
                  with actual type ‘Parser a’
    • The function ‘p’ is applied to one argument,
      but its type ‘Parser a’ has none
      In the expression: p inp
      In the expression:
        case p inp of {
          [] -> []
          [(v, out)] -> [(g v, out)] }
    • Relevant bindings include
        p :: Parser a (bound at src/Mailinglistproblem.hs:19:10)
        g :: a -> b (bound at src/Mailinglistproblem.hs:19:8)
        fmap :: (a -> b) -> Parser a -> Parser b


{
        name: Bogicevic Sasa
        phone: +381606006200
}



> On Aug 4, 2017, at 22:02, Jeffrey Brown <[hidden email]> wrote:
>
> If you post there, you could put the link on this thread; I'd be interested.
>
> On Fri, Aug 4, 2017 at 3:04 PM, Yassine <[hidden email]> wrote:
> Ok, thanks for your answer
>
> 2017-08-04 20:04 GMT+02:00 David McBride <[hidden email]>:
> > This is a bit complicated for this list.  You might have a bit more
> > luck posting this to stackoverflow.com.
> >
> > On Thu, Aug 3, 2017 at 3:19 PM, Yassine <[hidden email]> wrote:
> >> 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
> >> [hidden email]
> >> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
> > _______________________________________________
> > Beginners mailing list
> > [hidden email]
> > http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
>
> --
> Jeff Brown | Jeffrey Benjamin Brown
> Website   |   Facebook   |   LinkedIn(spammy, so I often miss messages here)   |   Github  
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Applicative: how <*> really works

sasa bogicevic
In reply to this post by Jeffrey Brown
Ok there was a constructor missing, maybe you should create a gist so we can help out

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

{
        name: Bogicevic Sasa
        phone: +381606006200
}



> On Aug 4, 2017, at 22:02, Jeffrey Brown <[hidden email]> wrote:
>
> If you post there, you could put the link on this thread; I'd be interested.
>
> On Fri, Aug 4, 2017 at 3:04 PM, Yassine <[hidden email]> wrote:
> Ok, thanks for your answer
>
> 2017-08-04 20:04 GMT+02:00 David McBride <[hidden email]>:
> > This is a bit complicated for this list.  You might have a bit more
> > luck posting this to stackoverflow.com.
> >
> > On Thu, Aug 3, 2017 at 3:19 PM, Yassine <[hidden email]> wrote:
> >> 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
> >> [hidden email]
> >> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
> > _______________________________________________
> > Beginners mailing list
> > [hidden email]
> > http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
>
> --
> Jeff Brown | Jeffrey Benjamin Brown
> Website   |   Facebook   |   LinkedIn(spammy, so I often miss messages here)   |   Github  
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Applicative: how <*> really works

Yassine
Here is the link to stackoverflow:
https://stackoverflow.com/questions/45514315/applicative-functor-and-partial-application-how-it-works


Sorry there is a mistake in the definition of fmap.
It is:
case parse p inp

and not:
case p inp


2017-08-04 22:10 GMT+02:00 sasa bogicevic <[hidden email]>:

> Ok there was a constructor missing, maybe you should create a gist so we can help out
>
> instance Functor Parser where
>   fmap g (P p) = P  (\inp -> case p inp of
>                          [] -> []
>                          [(v, out)] -> [(g v, out)])
>
> {
>         name: Bogicevic Sasa
>         phone: +381606006200
> }
>
>
>
>> On Aug 4, 2017, at 22:02, Jeffrey Brown <[hidden email]> wrote:
>>
>> If you post there, you could put the link on this thread; I'd be interested.
>>
>> On Fri, Aug 4, 2017 at 3:04 PM, Yassine <[hidden email]> wrote:
>> Ok, thanks for your answer
>>
>> 2017-08-04 20:04 GMT+02:00 David McBride <[hidden email]>:
>> > This is a bit complicated for this list.  You might have a bit more
>> > luck posting this to stackoverflow.com.
>> >
>> > On Thu, Aug 3, 2017 at 3:19 PM, Yassine <[hidden email]> wrote:
>> >> 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
>> >> [hidden email]
>> >> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>> > _______________________________________________
>> > Beginners mailing list
>> > [hidden email]
>> > http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>> _______________________________________________
>> Beginners mailing list
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>
>>
>>
>> --
>> Jeff Brown | Jeffrey Benjamin Brown
>> Website   |   Facebook   |   LinkedIn(spammy, so I often miss messages here)   |   Github
>> _______________________________________________
>> Beginners mailing list
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Applicative: how <*> really works

Ivan Llopard
In reply to this post by Yassine
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 <[hidden email]>:
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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: 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 <[hidden email]>:

> 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 <[hidden email]>:
>>
>> 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
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
>
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Applicative: how <*> really works

Ivan Llopard
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 <[hidden email]>:
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 <[hidden email]>:
> 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 <[hidden email]>:
>>
>> 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
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
>
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Loading...