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 <fa-ml@ariis.it> 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