Quantcast

applicative instance

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

applicative instance

sasa bogicevic
What is wrong with my applicative instance for custom List type ?

http://lpaste.net/351723

data List a = Nil | Cons a (List a) deriving (Eq, Show)



instance Applicative List where
    pure x = Cons x Nil
    Nil <*> _ = Nil
    _ <*> Nil = Nil
    (Cons x xy) <*> (Cons z dy)   =  Cons (x z)  (xy <*> dy)

Prelude> let functions = Cons (+1) (Cons (*2) Nil)
Prelude> let values = Cons 1 (Cons 2 Nil)
Prelude> functions <*> values
Cons 2 (Cons 3 (Cons 2 (Cons 4 Nil)))  -- I get Cons 2 (Cons 4 Nil) what is wrong with my Applicative instance ?


{
        name: Bogicevic Sasa
        phone: +381606006200
}



_______________________________________________
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 instance

Benjamin Edwards

You are zipping rather than taking the cross product.

Ben


On Fri, 27 Jan 2017, 22:09 sasa bogicevic, <[hidden email]> wrote:
What is wrong with my applicative instance for custom List type ?

http://lpaste.net/351723

data List a = Nil | Cons a (List a) deriving (Eq, Show)



instance Applicative List where
    pure x = Cons x Nil
    Nil <*> _ = Nil
    _ <*> Nil = Nil
    (Cons x xy) <*> (Cons z dy)   =  Cons (x z)  (xy <*> dy)

Prelude> let functions = Cons (+1) (Cons (*2) Nil)
Prelude> let values = Cons 1 (Cons 2 Nil)
Prelude> functions <*> values
Cons 2 (Cons 3 (Cons 2 (Cons 4 Nil)))  -- I get Cons 2 (Cons 4 Nil) what is wrong with my Applicative instance ?


{
        name: Bogicevic Sasa
        phone: +381606006200
}



_______________________________________________
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 instance

Francesco Ariis
In reply to this post by sasa bogicevic
On Fri, Jan 27, 2017 at 11:09:07PM +0100, sasa bogicevic wrote:
> What is wrong with my applicative instance for custom List type ?
>
> http://lpaste.net/351723
>
> [..]

You have implemented <*> on a list in one of the many possible
(and sensible) ways. In regular Haskell it's a ZipList

    λ> :m Control.Applicative
    λ> ZipList [(+1), (*2)] <*> ZipList [1,2]
    ZipList {getZipList = [2,4]}

(and there's nothing wrong with that)
_______________________________________________
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 instance

sasa bogicevic
Ok so how would the implementation look to get the correct result ?
I can't seem to write something that will compile except ZipList version.

Thanks, Sasa



> On Jan 27, 2017, at 23:21, Francesco Ariis <[hidden email]> wrote:
>
> On Fri, Jan 27, 2017 at 11:09:07PM +0100, sasa bogicevic wrote:
>> What is wrong with my applicative instance for custom List type ?
>>
>> http://lpaste.net/351723
>>
>> [..]
>
> You have implemented <*> on a list in one of the many possible
> (and sensible) ways. In regular Haskell it's a ZipList
>
>    λ> :m Control.Applicative
>    λ> ZipList [(+1), (*2)] <*> ZipList [1,2]
>    ZipList {getZipList = [2,4]}
>
> (and there's nothing wrong with that)
> _______________________________________________
> 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 instance

Francesco Ariis
On Sat, Jan 28, 2017 at 10:09:10AM +0100, sasa bogicevic wrote:
> Ok so how would the implementation look to get the correct result ?
> I can't seem to write something that will compile except ZipList version.

One way is by implementing your own (++):

    data List a = Nil | Cons a (List a) deriving (Eq, Show)

    plusPlus :: List a -> List a -> List a
    plusPlus Nil         bs = bs
    plusPlus (Cons a as) bs = Cons a (as `plusPlus` bs)

    instance Functor List where
        fmap f Nil = Nil
        fmap f (Cons a b) = Cons (f a) (fmap f b)

    instance Applicative List where
        pure x = Cons x Nil
        Nil <*> _ = Nil
        _ <*> Nil = Nil
        (Cons x xy) <*> ys = (fmap x ys) `plusPlus` (xy <*> ys)

_______________________________________________
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 instance

sasa bogicevic
Yep that worked, thanks.
Is there a way to do it without defining a separate function like plusPlus ?





> On Jan 28, 2017, at 10:43, Francesco Ariis <[hidden email]> wrote:
>
> On Sat, Jan 28, 2017 at 10:09:10AM +0100, sasa bogicevic wrote:
>> Ok so how would the implementation look to get the correct result ?
>> I can't seem to write something that will compile except ZipList version.
>
> One way is by implementing your own (++):
>
>    data List a = Nil | Cons a (List a) deriving (Eq, Show)
>
>    plusPlus :: List a -> List a -> List a
>    plusPlus Nil         bs = bs
>    plusPlus (Cons a as) bs = Cons a (as `plusPlus` bs)
>
>    instance Functor List where
>        fmap f Nil = Nil
>        fmap f (Cons a b) = Cons (f a) (fmap f b)
>
>    instance Applicative List where
>        pure x = Cons x Nil
>        Nil <*> _ = Nil
>        _ <*> Nil = Nil
>        (Cons x xy) <*> ys = (fmap x ys) `plusPlus` (xy <*> ys)
>
> _______________________________________________
> 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 instance

Graham Gill

On 28-Jan-2017 4:53 AM, sasa bogicevic wrote:
Is there a way to do it without defining a separate function like plusPlus ?

My guess is there isn't. I'm unsure what you mean by your question though.


Your List is a reimplementation of Haskell []. So, List with the "Cartesian product" Applicative instance will, like Haskell [], extend to a Monad instance. In the Monad instance for [], join = concat, and the work of concat is done using ++.

For List, we can implement join using concatList:

concatList :: List (List a) -> List a
concatList Nil = Nil
concatList (Cons xs xss) = xs `plusPlus` (concatList xss)

and then we can add a Monad instance for List:

instance Monad List where
    return = pure
    xs >>= f = concatList (pure f <*> xs)

or equivalently, bind is given by
    xs >>= f = concatList (fmap f xs)

To ask whether you can define the Cartesian product Applicative instance for List without plusPlus, is, I think, like asking whether there is a Cartesian product Applicative instance for List (or []) which doesn't extend to a Monad instance. Because if it does extend to a Monad (that obeys the Monad laws), then there will exist an implementation of join :: List (List a) -> List a, and join will need to collapse a List of Lists into a List. A function like plusPlus is used to accomplish the collapse.

That's "proof by hand waving."

The Ziplist Applicative instance for List on the other hand can't be extended to a Monad instance without additional restrictions on the lengths of the lists. Your question led me to some interesting reading with a google search on "list monad vs ziplist". Thanks.


On 28-Jan-2017 4:53 AM, sasa bogicevic wrote:
Yep that worked, thanks.
Is there a way to do it without defining a separate function like plusPlus ?





On Jan 28, 2017, at 10:43, Francesco Ariis [hidden email] wrote:

On Sat, Jan 28, 2017 at 10:09:10AM +0100, sasa bogicevic wrote:
Ok so how would the implementation look to get the correct result ?
I can't seem to write something that will compile except ZipList version.
One way is by implementing your own (++):

   data List a = Nil | Cons a (List a) deriving (Eq, Show)

   plusPlus :: List a -> List a -> List a
   plusPlus Nil         bs = bs
   plusPlus (Cons a as) bs = Cons a (as `plusPlus` bs)

   instance Functor List where
       fmap f Nil = Nil
       fmap f (Cons a b) = Cons (f a) (fmap f b)

   instance Applicative List where
       pure x = Cons x Nil
       Nil <*> _ = Nil
       _ <*> Nil = Nil
       (Cons x xy) <*> ys = (fmap x ys) `plusPlus` (xy <*> ys)

_______________________________________________
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 instance

sasa bogicevic
Wow thanks for the indepth explanation. I am glad that this got you reading some stuff but the fact is I was just doing an exercise in writing Applicative instances for some types and it was not stated that we should use separate 'helper' functions to achieve this. So I banged my head trying to write the correct implementation but I could only come up with the zipList solution. Thanks again!

Sasa


> On Jan 30, 2017, at 06:57, Graham Gill <[hidden email]> wrote:
>
>
> On 28-Jan-2017 4:53 AM, sasa bogicevic wrote:
>> Is there a way to do it without defining a separate function like plusPlus ?
>
> My guess is there isn't. I'm unsure what you mean by your question though.
>
> Your List is a reimplementation of Haskell []. So, List with the "Cartesian product" Applicative instance will, like Haskell [], extend to a Monad instance. In the Monad instance for [], join = concat, and the work of concat is done using ++.
>
> For List, we can implement join using concatList:
>
> concatList :: List (List a) -> List a
> concatList Nil = Nil
> concatList (Cons xs xss) = xs `plusPlus` (concatList xss)
>
> and then we can add a Monad instance for List:
>
> instance Monad List where
>     return = pure
>     xs >>= f = concatList (pure f <*> xs)
>
> or equivalently, bind is given by
>     xs >>= f = concatList (fmap f xs)
>
> To ask whether you can define the Cartesian product Applicative instance for List without plusPlus, is, I think, like asking whether there is a Cartesian product Applicative instance for List (or []) which doesn't extend to a Monad instance. Because if it does extend to a Monad (that obeys the Monad laws), then there will exist an implementation of join :: List (List a) -> List a, and join will need to collapse a List of Lists into a List. A function like plusPlus is used to accomplish the collapse.
>
> That's "proof by hand waving."
>
> The Ziplist Applicative instance for List on the other hand can't be extended to a Monad instance without additional restrictions on the lengths of the lists. Your question led me to some interesting reading with a google search on "list monad vs ziplist". Thanks.
>
>
> On 28-Jan-2017 4:53 AM, sasa bogicevic wrote:
>> Yep that worked, thanks.
>> Is there a way to do it without defining a separate function like plusPlus ?
>>
>>
>>
>>
>>
>>
>>> On Jan 28, 2017, at 10:43, Francesco Ariis <[hidden email]>
>>>  wrote:
>>>
>>> On Sat, Jan 28, 2017 at 10:09:10AM +0100, sasa bogicevic wrote:
>>>
>>>> Ok so how would the implementation look to get the correct result ?
>>>> I can't seem to write something that will compile except ZipList version.
>>>>
>>> One way is by implementing your own (++):
>>>
>>>    data List a = Nil | Cons a (List a) deriving (Eq, Show)
>>>
>>>    plusPlus :: List a -> List a -> List a
>>>    plusPlus Nil         bs = bs
>>>    plusPlus (Cons a as) bs = Cons a (as `plusPlus` bs)
>>>
>>>    instance Functor List where
>>>        fmap f Nil = Nil
>>>        fmap f (Cons a b) = Cons (f a) (fmap f b)
>>>
>>>    instance Applicative List where
>>>        pure x = Cons x Nil
>>>        Nil <*> _ = Nil
>>>        _ <*> Nil = Nil
>>>        (Cons x xy) <*> ys = (fmap x ys) `plusPlus` (xy <*> ys)
>>>
>>> _______________________________________________
>>> 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...