[Haskell-beginners] applicative instance
Graham Gill
math.simplex at gmail.com
Mon Jan 30 05:57:26 UTC 2017
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<fa-ml at 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 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/20170130/9a680355/attachment.html>
More information about the Beginners
mailing list