Applicative but not Monad

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
29 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Applicative but not Monad

Yusaku Hashimoto
Hello cafe,
Do you know any data-type which is Applicative but not Monad?

Cheers,
-~nwn
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Applicative but not Monad

Eugene Kirpichov
Yes. ZipList.
http://en.wikibooks.org/wiki/Haskell/Applicative_Functors

2009/10/30 Yusaku Hashimoto <[hidden email]>:

> Hello cafe,
> Do you know any data-type which is Applicative but not Monad?
>
> Cheers,
> -~nwn
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>



--
Eugene Kirpichov
Web IR developer, market.yandex.ru
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Applicative but not Monad

Thomas Davie
Of note, there is a sensible monad instance for zip lists which I *think* agrees with the Applicative one, I don't know why they're not monads:

instance Monad (ZipList a) where
  return = Ziplist . return
  join (ZipList []) = ZipList []
  join (ZipList (a:as)) = zlHead a `zlCons` join (map zlTail as)

I'll provide an alternative though, Const a is an applicative, but not a monad.

Bob

On Fri, Oct 30, 2009 at 5:25 PM, Eugene Kirpichov <[hidden email]> wrote:
Yes. ZipList.
http://en.wikibooks.org/wiki/Haskell/Applicative_Functors

2009/10/30 Yusaku Hashimoto <[hidden email]>:
> Hello cafe,
> Do you know any data-type which is Applicative but not Monad?
>
> Cheers,
> -~nwn
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>



--
Eugene Kirpichov
Web IR developer, market.yandex.ru
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Applicative but not Monad

Luke Palmer-2
On Fri, Oct 30, 2009 at 10:39 AM, Tom Davie <[hidden email]> wrote:
> Of note, there is a sensible monad instance for zip lists which I *think*
> agrees with the Applicative one, I don't know why they're not monads:
> instance Monad (ZipList a) where
>   return = Ziplist . return
>   join (ZipList []) = ZipList []
>   join (ZipList (a:as)) = zlHead a `zlCons` join (map zlTail as)

IIRC, that doesn't satisfy the associativity law, particularly when
you are joining a list of lists of different lengths.  2 minutes of
experimenting failed to find me the counterexample though.
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Applicative but not Monad

Thomas Davie
On Fri, Oct 30, 2009 at 5:59 PM, Luke Palmer <[hidden email]> wrote:
On Fri, Oct 30, 2009 at 10:39 AM, Tom Davie <[hidden email]> wrote:
> Of note, there is a sensible monad instance for zip lists which I *think*
> agrees with the Applicative one, I don't know why they're not monads:
> instance Monad (ZipList a) where
>   return = Ziplist . return
>   join (ZipList []) = ZipList []
>   join (ZipList (a:as)) = zlHead a `zlCons` join (map zlTail as)

IIRC, that doesn't satisfy the associativity law, particularly when
you are joining a list of lists of different lengths.  2 minutes of
experimenting failed to find me the counterexample though.

Cool, thanks Luke, that explains why this is available in Stream, but not in ZipList too.

Bob

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Applicative but not Monad

David Menendez-2
In reply to this post by Luke Palmer-2
On Fri, Oct 30, 2009 at 12:59 PM, Luke Palmer <[hidden email]> wrote:

> On Fri, Oct 30, 2009 at 10:39 AM, Tom Davie <[hidden email]> wrote:
>> Of note, there is a sensible monad instance for zip lists which I *think*
>> agrees with the Applicative one, I don't know why they're not monads:
>> instance Monad (ZipList a) where
>>   return = Ziplist . return
>>   join (ZipList []) = ZipList []
>>   join (ZipList (a:as)) = zlHead a `zlCons` join (map zlTail as)
>
> IIRC, that doesn't satisfy the associativity law, particularly when
> you are joining a list of lists of different lengths.  2 minutes of
> experimenting failed to find me the counterexample though.

This works fine for infinite lists, since an infinite list is
equivalent to Nat -> a.

With finite lists, this implementation hits problems with calling head
on empty lists. If I rewrite it to avoid that problem, the
associativity law fails.

tail' [] = []
tail' (_:as) = as

diag ((a:_):bs) = a : diag (map tail' bs)
diag _ = []

bind :: [Int] -> (Int -> [Int]) -> [Int]  -- monomorphic for QuickCheck
bind m f = diag (map f m)

Prelude Test.QuickCheck Test.QuickCheck.Function> quickCheck $ \m
(Function _ f) (Function _ g) -> bind (bind m f) g == bind m (\x ->
bind (f x) g)
*** Failed! Falsifiable (after 16 tests and 23 shrinks):
[1,0]
{0 -> [-13,0], 1 -> [0]}
{-13 -> [], 0 -> [0,0]}

The left side is [0,0], the right side is [0].

--
Dave Menendez <[hidden email]>
<http://www.eyrie.org/~zednenem/>
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Applicative but not Monad

Yusaku Hashimoto
In reply to this post by Thomas Davie
Thanks for fast replies! Examples you gave explain why all
Applicatives are not Monads to me.

And I tried to rewrite Bob's Monad instance for ZipList with (>>=).

import Control.Applicative

instance Monad ZipList where
  return = ZipList . return
  (ZipList []) >>= _ = ZipList []
  (ZipList (a:as)) >>= f = zlHead (f a) `zlCons` (ZipList as >>= f)

zlHead :: ZipList a -> a
zlHead (ZipList (a:_)) = a
zlCons :: a -> ZipList a -> ZipList a
zlCons a (ZipList as) = ZipList $ a:as
zlTail :: ZipList a -> ZipList a
zlTail (ZipList (_:as)) = ZipList as

I understand if this instance satisfies the laws, we can replace <$>
with `liftM` and <*> and `ap`. And I found a counterexample (correct
me if I'm wrong).

*Main Control.Monad> getZipList $ (*) <$> ZipList [1,2] <*> ZipList [3,4,5]
[3,8]
*Main Control.Monad> getZipList $ (*) `liftM` ZipList [1,2] `ap` ZipList [3,4,5]
[3,6]

Cheers,
-~nwn

On Sat, Oct 31, 2009 at 2:06 AM, Tom Davie <[hidden email]> wrote:

> On Fri, Oct 30, 2009 at 5:59 PM, Luke Palmer <[hidden email]> wrote:
>>
>> On Fri, Oct 30, 2009 at 10:39 AM, Tom Davie <[hidden email]> wrote:
>> > Of note, there is a sensible monad instance for zip lists which I
>> > *think*
>> > agrees with the Applicative one, I don't know why they're not monads:
>> > instance Monad (ZipList a) where
>> >   return = Ziplist . return
>> >   join (ZipList []) = ZipList []
>> >   join (ZipList (a:as)) = zlHead a `zlCons` join (map zlTail as)
>>
>> IIRC, that doesn't satisfy the associativity law, particularly when
>> you are joining a list of lists of different lengths.  2 minutes of
>> experimenting failed to find me the counterexample though.
>
> Cool, thanks Luke, that explains why this is available in Stream, but not in
> ZipList too.
> Bob
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Applicative but not Monad

David Menendez-2
On Fri, Oct 30, 2009 at 1:33 PM, Yusaku Hashimoto <[hidden email]> wrote:

> Thanks for fast replies! Examples you gave explain why all
> Applicatives are not Monads to me.
>
> And I tried to rewrite Bob's Monad instance for ZipList with (>>=).
>
> import Control.Applicative
>
> instance Monad ZipList where
>  return = ZipList . return
>  (ZipList []) >>= _ = ZipList []
>  (ZipList (a:as)) >>= f = zlHead (f a) `zlCons` (ZipList as >>= f)

This is taking the first element of each list, but you need to take
the nth element. Try

  (ZipList (a:as)) >>= f = zlHead (f a) `zlCons` (ZipList as >>= zlTail . f)


--
Dave Menendez <[hidden email]>
<http://www.eyrie.org/~zednenem/>
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Applicative but not Monad

Yusaku Hashimoto
Thank you for your correction. I tried your (>>=) and replaced
return's definition with

return = ZipList . repeat

then as you said this works fine for infinite lists.

Cheers,
-~nwn

On Sat, Oct 31, 2009 at 2:39 AM, David Menendez <[hidden email]> wrote:

> On Fri, Oct 30, 2009 at 1:33 PM, Yusaku Hashimoto <[hidden email]> wrote:
>> Thanks for fast replies! Examples you gave explain why all
>> Applicatives are not Monads to me.
>>
>> And I tried to rewrite Bob's Monad instance for ZipList with (>>=).
>>
>> import Control.Applicative
>>
>> instance Monad ZipList where
>>  return = ZipList . return
>>  (ZipList []) >>= _ = ZipList []
>>  (ZipList (a:as)) >>= f = zlHead (f a) `zlCons` (ZipList as >>= f)
>
> This is taking the first element of each list, but you need to take
> the nth element. Try
>
>  (ZipList (a:as)) >>= f = zlHead (f a) `zlCons` (ZipList as >>= zlTail . f)
>
>
> --
> Dave Menendez <[hidden email]>
> <http://www.eyrie.org/~zednenem/>
>
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Applicative but not Monad

Dan Weston
In reply to this post by Thomas Davie
Can you elaborate on why Const is not a monad?

return x = Const x
fmap f (Const x) = Const (f x)
join (Const (Const x)) = Const x

What am I missing?

Tom Davie wrote:

> Of note, there is a sensible monad instance for zip lists which I
> *think* agrees with the Applicative one, I don't know why they're not
> monads:
>
> instance Monad (ZipList a) where
>   return = Ziplist . return
>   join (ZipList []) = ZipList []
>   join (ZipList (a:as)) = zlHead a `zlCons` join (map zlTail as)
>
> I'll provide an alternative though, Const a is an applicative, but not a
> monad.
>
> Bob
>
> On Fri, Oct 30, 2009 at 5:25 PM, Eugene Kirpichov <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     Yes. ZipList.
>     http://en.wikibooks.org/wiki/Haskell/Applicative_Functors
>
>     2009/10/30 Yusaku Hashimoto <[hidden email]
>     <mailto:[hidden email]>>:
>      > Hello cafe,
>      > Do you know any data-type which is Applicative but not Monad?
>      >
>      > Cheers,
>      > -~nwn
>      > _______________________________________________
>      > Haskell-Cafe mailing list
>      > [hidden email] <mailto:[hidden email]>
>      > http://www.haskell.org/mailman/listinfo/haskell-cafe
>      >
>
>
>
>     --
>     Eugene Kirpichov
>     Web IR developer, market.yandex.ru <http://market.yandex.ru>
>     _______________________________________________
>     Haskell-Cafe mailing list
>     [hidden email] <mailto:[hidden email]>
>     http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Applicative but not Monad

MigMit
What type is your "return"?

On 30 Oct 2009, at 21:48, Dan Weston wrote:

> Can you elaborate on why Const is not a monad?
>
> return x = Const x
> fmap f (Const x) = Const (f x)
> join (Const (Const x)) = Const x
>
> What am I missing?
>
> Tom Davie wrote:
>> Of note, there is a sensible monad instance for zip lists which I  
>> *think* agrees with the Applicative one, I don't know why they're  
>> not monads:
>> instance Monad (ZipList a) where
>>  return = Ziplist . return
>>  join (ZipList []) = ZipList []
>>  join (ZipList (a:as)) = zlHead a `zlCons` join (map zlTail as)
>> I'll provide an alternative though, Const a is an applicative, but  
>> not a monad.
>> Bob
>> On Fri, Oct 30, 2009 at 5:25 PM, Eugene Kirpichov <[hidden email]
>>  <mailto:[hidden email]>> wrote:
>>    Yes. ZipList.
>>    http://en.wikibooks.org/wiki/Haskell/Applicative_Functors
>>    2009/10/30 Yusaku Hashimoto <[hidden email]
>>    <mailto:[hidden email]>>:
>>     > Hello cafe,
>>     > Do you know any data-type which is Applicative but not Monad?
>>     >
>>     > Cheers,
>>     > -~nwn
>>     > _______________________________________________
>>     > Haskell-Cafe mailing list
>>     > [hidden email] <mailto:[hidden email]>
>>     > http://www.haskell.org/mailman/listinfo/haskell-cafe
>>     >
>>    --
>>    Eugene Kirpichov
>>    Web IR developer, market.yandex.ru <http://market.yandex.ru>
>>    _______________________________________________
>>    Haskell-Cafe mailing list
>>    [hidden email] <mailto:[hidden email]>
>>    http://www.haskell.org/mailman/listinfo/haskell-cafe
>
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Applicative but not Monad

Martijn van Steenbergen-2
In reply to this post by Yusaku Hashimoto
Yusaku Hashimoto wrote:
> Hello cafe,
> Do you know any data-type which is Applicative but not Monad?

The Except datatype defined in the Applicative paper.

Some parsers are not monads, allowing for optimizations.

Martijn.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Applicative but not Monad

Jeremy Shaw-3
In reply to this post by Yusaku Hashimoto
Formlets are not Monads.

http://www.haskell.org/haskellwiki/Formlets

If you tried, you could actually implement a Monad instance for  
Formlets, but it would lead to very undesirable behavior.  Specially,  
if a field in the form failed to validate, then the rest of the form  
would not be rendered at all.

- jeremy



On Oct 30, 2009, at 11:14 AM, Yusaku Hashimoto wrote:

> Hello cafe,
> Do you know any data-type which is Applicative but not Monad?
>
> Cheers,
> -~nwn
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Applicative but not Monad

Job Vranish
In reply to this post by Yusaku Hashimoto
If you use a monad instance for ZipLists as follows:

instance Monad ZipList where
  return x = ZipList $ repeat x
  ZipList [] >>= _ = ZipList []
  xs >>= f = diagonal $ fmap f xs

(where diagonal pulls out the diagonal elements of a ziplist of ziplists)

It will satisfy all the monad laws _except_ when the function f (in xs >>= f) returns ziplists of different length depending on the value passed to it. If f always returns lists of the same length, the monad laws should still hold even if the lists are not infinite in length.


I have a fixed size list type (http://github.com/jvranish/FixedList) that uses an instance like this and it always satisfies the monad laws since the length of the list can be determined from the type so f is forced to always return the same size of list.

I hope that helps things make sense :)

- Job



On Fri, Oct 30, 2009 at 1:33 PM, Yusaku Hashimoto <[hidden email]> wrote:
Thanks for fast replies! Examples you gave explain why all
Applicatives are not Monads to me.

And I tried to rewrite Bob's Monad instance for ZipList with (>>=).

import Control.Applicative

instance Monad ZipList where
 return = ZipList . return
 (ZipList []) >>= _ = ZipList []
 (ZipList (a:as)) >>= f = zlHead (f a) `zlCons` (ZipList as >>= f)

zlHead :: ZipList a -> a
zlHead (ZipList (a:_)) = a
zlCons :: a -> ZipList a -> ZipList a
zlCons a (ZipList as) = ZipList $ a:as
zlTail :: ZipList a -> ZipList a
zlTail (ZipList (_:as)) = ZipList as

I understand if this instance satisfies the laws, we can replace <$>
with `liftM` and <*> and `ap`. And I found a counterexample (correct
me if I'm wrong).

*Main Control.Monad> getZipList $ (*) <$> ZipList [1,2] <*> ZipList [3,4,5]
[3,8]
*Main Control.Monad> getZipList $ (*) `liftM` ZipList [1,2] `ap` ZipList [3,4,5]
[3,6]

Cheers,
-~nwn

On Sat, Oct 31, 2009 at 2:06 AM, Tom Davie <[hidden email]> wrote:
> On Fri, Oct 30, 2009 at 5:59 PM, Luke Palmer <[hidden email]> wrote:
>>
>> On Fri, Oct 30, 2009 at 10:39 AM, Tom Davie <[hidden email]> wrote:
>> > Of note, there is a sensible monad instance for zip lists which I
>> > *think*
>> > agrees with the Applicative one, I don't know why they're not monads:
>> > instance Monad (ZipList a) where
>> >   return = Ziplist . return
>> >   join (ZipList []) = ZipList []
>> >   join (ZipList (a:as)) = zlHead a `zlCons` join (map zlTail as)
>>
>> IIRC, that doesn't satisfy the associativity law, particularly when
>> you are joining a list of lists of different lengths.  2 minutes of
>> experimenting failed to find me the counterexample though.
>
> Cool, thanks Luke, that explains why this is available in Stream, but not in
> ZipList too.
> Bob
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Applicative but not Monad

Yusaku Hashimoto
In reply to this post by Martijn van Steenbergen-2
> Some parsers are not monads, allowing for optimizations.

Could you elaborate on them or give me some pointers? I think I heard
about it two or three times, but I couldn't find any resource of them.

-~nwn

On Sat, Oct 31, 2009 at 5:35 AM, Martijn van Steenbergen
<[hidden email]> wrote:

> Yusaku Hashimoto wrote:
>>
>> Hello cafe,
>> Do you know any data-type which is Applicative but not Monad?
>
> The Except datatype defined in the Applicative paper.
>
> Some parsers are not monads, allowing for optimizations.
>
> Martijn.
>
>
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Applicative but not Monad

Tony Morris-4
In reply to this post by Yusaku Hashimoto
newtype Accy o a = Acc{acc :: o } -- Applicative Programming With Effects


Yusaku Hashimoto wrote:

> Hello cafe,
> Do you know any data-type which is Applicative but not Monad?
>
> Cheers,
> -~nwn
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>  

--
Tony Morris
http://tmorris.net/


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Applicative but not Monad

Heinrich Apfelmus
In reply to this post by Dan Weston
Dan Weston wrote:
> Can you elaborate on why Const is not a monad?
>
> return x = Const x
> fmap f (Const x) = Const (f x)
> join (Const (Const x)) = Const x
>

This is not  Const , this is the  Identity  monad.

The real  Const  looks like this:

   newtype Const b a = Const b

   instance Monoid b => Applicative (Const b) where
        pure x = Const mempty
        (Const b) <*> (Const b') = Const (b `mappend` b')

The only possible monad instance would be

   return x = Const mempty
   fmap f (Const b) = Const b
   join (Const b)   = Const b

but that's not just  ()  turned into a monad.


Regards,
apfelmus

--
http://apfelmus.nfshost.com

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Applicative but not Monad

Conor McBride-2
In reply to this post by Yusaku Hashimoto
Hi

On 30 Oct 2009, at 16:14, Yusaku Hashimoto wrote:

> Hello cafe,
> Do you know any data-type which is Applicative but not Monad?

[can resist anything but temptation]

I have an example, perhaps not a datatype:
  tomorrow-you-will-know

Cheers

Conor

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: Applicative but not Monad

Thomas Davie
In reply to this post by Heinrich Apfelmus
On 10/31/09, Heinrich Apfelmus <[hidden email]> wrote:
> The only possible monad instance would be
>
>    return x = Const mempty
>    fmap f (Const b) = Const b
>    join (Const b)   = Const b

Your join doesn't seem to have the right type... Unless I'm missing something.

Bob
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: Applicative but not Monad

Daniel Fischer-4
Am Samstag 31 Oktober 2009 12:25:17 schrieb Tom Davie:

> On 10/31/09, Heinrich Apfelmus <[hidden email]> wrote:
> > The only possible monad instance would be
> >
> >    return x = Const mempty
> >    fmap f (Const b) = Const b
> >    join (Const b)   = Const b
>
> Your join doesn't seem to have the right type... Unless I'm missing
> something.
>
> Bob

join (Const b :: Const b (Const b a)) = (Const b :: Const b a)
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
12