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
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[jkff]

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

2009/10/30 Yusaku Hashimoto <nonowarn@...>:

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

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

[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 <ekirpichov@...> wrote:

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

2009/10/30 Yusaku Hashimoto <nonowarn@...>:

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

--
Eugene Kirpichov
Web IR developer, market.yandex.ru

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Luke Palmer-2]

On Fri, Oct 30, 2009 at 10:39 AM, Tom Davie <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)

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
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Thomas Davie]

On Fri, Oct 30, 2009 at 5:59 PM, Luke Palmer <lrpalmer@...> wrote:

On Fri, Oct 30, 2009 at 10:39 AM, Tom Davie <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)

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
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[David Menendez-2]

On Fri, Oct 30, 2009 at 12:59 PM, Luke Palmer <lrpalmer@...> wrote:

> On Fri, Oct 30, 2009 at 10:39 AM, Tom Davie <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)
>
> 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 <dave@...>
<http://www.eyrie.org/~zednenem/>
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Yusaku Hashimoto]

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 <tom.davie@...> wrote:

> On Fri, Oct 30, 2009 at 5:59 PM, Luke Palmer <lrpalmer@...> wrote:
>>
>> On Fri, Oct 30, 2009 at 10:39 AM, Tom Davie <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)
>>
>> 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
> Haskell-Cafe@...
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[David Menendez-2]

On Fri, Oct 30, 2009 at 1:33 PM, Yusaku Hashimoto <nonowarn@...> 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 <dave@...>
<http://www.eyrie.org/~zednenem/>
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[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 <dave@...> wrote:

> On Fri, Oct 30, 2009 at 1:33 PM, Yusaku Hashimoto <nonowarn@...> 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 <dave@...>
> <http://www.eyrie.org/~zednenem/>
>

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Dan Weston]

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 <ekirpichov@...
> <mailto:ekirpichov@...>> wrote:
>
>     Yes. ZipList.
>     http://en.wikibooks.org/wiki/Haskell/Applicative_Functors
>
>     2009/10/30 Yusaku Hashimoto <nonowarn@...
>     <mailto:nonowarn@...>>:
>      > Hello cafe,
>      > Do you know any data-type which is Applicative but not Monad?
>      >
>      > Cheers,
>      > -~nwn
>      > _______________________________________________
>      > Haskell-Cafe mailing list
>      > Haskell-Cafe@... <mailto:Haskell-Cafe@...>
>      > http://www.haskell.org/mailman/listinfo/haskell-cafe
>      >
>
>
>
>     --
>     Eugene Kirpichov
>     Web IR developer, market.yandex.ru <http://market.yandex.ru>
>     _______________________________________________
>     Haskell-Cafe mailing list
>     Haskell-Cafe@... <mailto:Haskell-Cafe@...>
>     http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Miguel Mitrofanov]

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 <ekirpichov@...
>>  <mailto:ekirpichov@...>> wrote:
>>    Yes. ZipList.
>>    http://en.wikibooks.org/wiki/Haskell/Applicative_Functors
>>    2009/10/30 Yusaku Hashimoto <nonowarn@...
>>    <mailto:nonowarn@...>>:
>>     > Hello cafe,
>>     > Do you know any data-type which is Applicative but not Monad?
>>     >
>>     > Cheers,
>>     > -~nwn
>>     > _______________________________________________
>>     > Haskell-Cafe mailing list
>>     > Haskell-Cafe@... <mailto:Haskell-Cafe@...>
>>     > http://www.haskell.org/mailman/listinfo/haskell-cafe
>>     >
>>    --
>>    Eugene Kirpichov
>>    Web IR developer, market.yandex.ru <http://market.yandex.ru>
>>    _______________________________________________
>>    Haskell-Cafe mailing list
>>    Haskell-Cafe@... <mailto:Haskell-Cafe@...>
>>    http://www.haskell.org/mailman/listinfo/haskell-cafe
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe@...
> http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Martijn van Steenbergen-2]

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
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Jeremy Shaw-3]

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
> Haskell-Cafe@...
> http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Job Vranish]

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 <nonowarn@...> 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 <tom.davie@...> wrote:
> On Fri, Oct 30, 2009 at 5:59 PM, Luke Palmer <lrpalmer@...> wrote:
>>
>> On Fri, Oct 30, 2009 at 10:39 AM, Tom Davie <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)
>>
>> 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
> Haskell-Cafe@...
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Yusaku Hashimoto]

> 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
<martijn@...> 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
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Tony Morris-4]

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
> Haskell-Cafe@...
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>  

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


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Heinrich Apfelmus]

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
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Conor McBride-2]

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
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Thomas Davie]

On 10/31/09, Heinrich Apfelmus <apfelmus@...> 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
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Daniel Fischer-4]

Am Samstag 31 Oktober 2009 12:25:17 schrieb Tom Davie:

> On 10/31/09, Heinrich Apfelmus <apfelmus@...> 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
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe