applicative instance

newer
Question about example in 'using...

older
Re: [Haskell-beginners] Ambiguous...

sasa bogicevic

27 Jan 2017 27 Jan '17

5:09 p.m.

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 }

Show replies by date

Benjamin Edwards

27 Jan 27 Jan

5:17 p.m.

You are zipping rather than taking the cross product. Ben On Fri, 27 Jan 2017, 22:09 sasa bogicevic, 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 Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

Francesco Ariis

5:21 p.m.

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)

sasa bogicevic

28 Jan 28 Jan

4:09 a.m.

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

Francesco Ariis

4:43 a.m.

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)

sasa bogicevic

4:53 a.m.

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

Graham Gill

30 Jan 30 Jan

12:57 a.m.

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 isgiven 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 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 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

sasa bogicevic

3:48 a.m.

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

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

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

3031

Age (days ago)

3034

Last active (days ago)

List overview

Download

7 comments

4 participants

participants (4)

Benjamin Edwards
Francesco Ariis
Graham Gill
sasa bogicevic