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
|

Re: Re: Applicative but not Monad

David Menendez-2
On Sat, Oct 31, 2009 at 6:22 AM, Heinrich Apfelmus
<[hidden email]> wrote:

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

This is inconsistent with the Applicative instance given above.

Const a <*> Const b = Const (a `mappend` b)

Const a `ap` Const b = Const a

In other words, Const has at least two Applicative instances, one of
which is not also a monad.

--
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: Re: Applicative but not Monad

Ryan Ingram
On Sat, Oct 31, 2009 at 8:38 AM, David Menendez <[hidden email]> wrote:
On Sat, Oct 31, 2009 at 6:22 AM, 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
>
> but that's not just  ()  turned into a monad.

This is inconsistent with the Applicative instance given above.

Const a <*> Const b = Const (a `mappend` b)

Const a `ap` Const b = Const a

In other words, Const has at least two Applicative instances, one of
which is not also a monad.

But this "Monad" instance isn't a monad either:

f True = Const [1]
f False = Const [2]

return True >>= f
{- by monad laws -}
= f True
= Const [1]

but by this code

return True >>= f
{- apply return, monoid [a] -}
= Const [] >>= f
{- definition of >>= -}
= join (fmap f (Const []))
{- apply join and fmap -}
= Const []


_______________________________________________
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 Conor McBride-2
Hi

On 31 Oct 2009, at 10:39, Conor McBride wrote:

> 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

Elaborating, one day later,

   if you know something today, you can arrange to know it tomorrow
   if will know a function tomorrow and its argument tomorrow, you
     can apply them tomorrow
   but if you will know tomorrow that you will know something the
     day after, that does not tell you how to know the thing tomorrow

Put otherwise, unit-delay is applicative but not monadic. I've been
using this to organise exactly what happens when in those wacky
miraculous-looking circular programs. It seems quite promising,
so far...

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: Applicative but not Monad

Henning Thielemann-4
In reply to this post by Yusaku Hashimoto
Yusaku Hashimoto schrieb:
> Hello cafe,
> Do you know any data-type which is Applicative but not Monad?

Here you also find an example:
http://www.haskell.org/haskellwiki/Applicative_functor

_______________________________________________
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 Conor McBride-2
On Sun, Nov 1, 2009 at 11:20 AM, Conor McBride
<[hidden email]> wrote:

> On 31 Oct 2009, at 10:39, Conor McBride wrote:
>> 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
>
> Elaborating, one day later,
>
>  if you know something today, you can arrange to know it tomorrow
>  if will know a function tomorrow and its argument tomorrow, you
>    can apply them tomorrow
>  but if you will know tomorrow that you will know something the
>    day after, that does not tell you how to know the thing tomorrow
>
> Put otherwise, unit-delay is applicative but not monadic. I've been
> using this to organise exactly what happens when in those wacky
> miraculous-looking circular programs. It seems quite promising,
> so far...

Can you do that with just applicative functors, or do you need arrows?

According to "Idioms are oblivious, arrows are meticulous, monads are
promiscuous"[1], an arrow (~>) that's equivalent to an applicative
functor has the property that "a ~> b" is isomorphic to "() ~> (a ->
b)".

A typical delay arrow has the form delay :: a -> (a ~> a), so if (~>)
is equivalent to some applicative functor f, we can rewrite that as
delay :: a -> f (a -> a), which seems too limited to have the proper
behavior.


[1] http://homepages.inf.ed.ac.uk/wadler/topics/links.html#arrows-and-idioms

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

Ross Paterson
In reply to this post by Conor McBride-2
On Sun, Nov 01, 2009 at 04:20:18PM +0000, Conor McBride wrote:

> On 31 Oct 2009, at 10:39, Conor McBride wrote:
> >I have an example, perhaps not a datatype:
> >tomorrow-you-will-know
>
> Elaborating, one day later,
>
>   if you know something today, you can arrange to know it tomorrow
>   if will know a function tomorrow and its argument tomorrow, you
>     can apply them tomorrow
>   but if you will know tomorrow that you will know something the
>     day after, that does not tell you how to know the thing tomorrow

Yes, but if you will know tomorrow that you will know something
tomorrow, then you will know that thing tomorrow.

The applicative does coincide with a monad, just not the one you first
thought of (or/max rather than plus).
_______________________________________________
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

On 2 Nov 2009, at 00:11, Ross Paterson wrote:

> On Sun, Nov 01, 2009 at 04:20:18PM +0000, Conor McBride wrote:
>> On 31 Oct 2009, at 10:39, Conor McBride wrote:
>>> I have an example, perhaps not a datatype:
>>> tomorrow-you-will-know
>>
>> Elaborating, one day later,
>>
>>  if you know something today, you can arrange to know it tomorrow
>>  if will know a function tomorrow and its argument tomorrow, you
>>    can apply them tomorrow
>>  but if you will know tomorrow that you will know something the
>>    day after, that does not tell you how to know the thing tomorrow
>
> Yes, but if you will know tomorrow that you will know something
> tomorrow, then you will know that thing tomorrow.

That depends on what "tomorrow" means tomorrow.

> The applicative does coincide with a monad, just not the one you first
> thought of (or/max rather than plus).

True, but it's not the notion I need to analyse circular programs.
I'm looking for something with a fixpoint operator

   fix :: (Tomorrow x -> x) -> x

which I can hopefully use to define things like

   repmin :: Tree Int -> (Int, Tomorrow (Tree Int))

so that the fixpoint operator gives me a Tomorrow Int which I
can use to build the second component, but ensures that the
black-hole-tastic Tomorrow (Tomorrow (Tree Int)) I also receive
is too late to be a serious temptation.

All the best

Conor

_______________________________________________
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
Obviously you know what your talking about and I don't, so this is a
question purely out of ignorance.

It seems to me that Tomorrow cannot be parametrically polymorphic, or
else I could wrap it again (Tomorrow (Tomorrox x)). An unwrapping
fixpoint operator needs to reflect the type to know when not to go too
far. One solution is to guarantee that it can go as far as it wants with
a comonad (stopping when the function argument wants to, not when the
data type runs out of data):

import Control.Comonad
import Control.Monad.Fix

tfix :: Comonad tomorrow => (tomorrow x -> x) -> x
tfix = extract . (\f -> fix (extend f))

To quote Cabaret, if tomorrow belongs to me, then surely the day after
belongs to me as well.

Otherwise, to stop the fixpoint, it seems you need a more restricted
type to encode some stopping sentinel (my own parametrically polymorphic
attempts all end in infinite types, so maybe ad hoc polymorphism or a
type witness is needed?)

Do you have a blog post on this problem?

Dan

Conor McBride wrote:

> On 2 Nov 2009, at 00:11, Ross Paterson wrote:
>
>> On Sun, Nov 01, 2009 at 04:20:18PM +0000, Conor McBride wrote:
>>> On 31 Oct 2009, at 10:39, Conor McBride wrote:
>>>> I have an example, perhaps not a datatype:
>>>> tomorrow-you-will-know
>>> Elaborating, one day later,
>>>
>>>  if you know something today, you can arrange to know it tomorrow
>>>  if will know a function tomorrow and its argument tomorrow, you
>>>    can apply them tomorrow
>>>  but if you will know tomorrow that you will know something the
>>>    day after, that does not tell you how to know the thing tomorrow
>> Yes, but if you will know tomorrow that you will know something
>> tomorrow, then you will know that thing tomorrow.
>
> That depends on what "tomorrow" means tomorrow.
>
>> The applicative does coincide with a monad, just not the one you first
>> thought of (or/max rather than plus).
>
> True, but it's not the notion I need to analyse circular programs.
> I'm looking for something with a fixpoint operator
>
>    fix :: (Tomorrow x -> x) -> x
>
> which I can hopefully use to define things like
>
>    repmin :: Tree Int -> (Int, Tomorrow (Tree Int))
>
> so that the fixpoint operator gives me a Tomorrow Int which I
> can use to build the second component, but ensures that the
> black-hole-tastic Tomorrow (Tomorrow (Tree Int)) I also receive
> is too late to be a serious temptation.
>
> All the best
>
> Conor
>
> _______________________________________________
> 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

Dan Doel
On Monday 02 November 2009 2:56:45 pm Dan Weston wrote:
> It seems to me that Tomorrow cannot be parametrically polymorphic, or
> else I could wrap it again (Tomorrow (Tomorrox x)). An unwrapping
> fixpoint operator needs to reflect the type to know when not to go too
> far. One solution is to guarantee that it can go as far as it wants with
> a comonad (stopping when the function argument wants to, not when the
> data type runs out of data):

He isn't worried about people putting things off; he's worried about people
using things sooner than they're ready. So:

> import Control.Comonad
> import Control.Monad.Fix
>
> tfix :: Comonad tomorrow => (tomorrow x -> x) -> x
> tfix = extract . (\f -> fix (extend f))

This doesn't achieve his goals, because:

  tfix extract

tries to get the 'x' from tomorrow and give it to you today, which is bad, and
of course:

  tfix extract = extract (fix (extend extract)) = extract (fix id)
               = extract _|_ =? _|_

Rather, the aim is to give you a promise of something tomorrow, so that you
can build a structure made of something today, followed by something tomorrow.
That is, roughly, enforcing the productive construction of a circular object.
Such a productive process is given the object 'in the future', and it must
produce something now, followed (in time) by operations on the future whole.

And the problem with monads is that Tomorrow (Tomorrow x) is something that
happens in two days, but join is supposed to make it happen tomorrow instead.

> To quote Cabaret, if tomorrow belongs to me, then surely the day after
> belongs to me as well.
>
> Otherwise, to stop the fixpoint, it seems you need a more restricted
> type to encode some stopping sentinel (my own parametrically polymorphic
> attempts all end in infinite types, so maybe ad hoc polymorphism or a
> type witness is needed?)
>
> Do you have a blog post on this problem?

He does, in fact:

  http://www.e-pig.org/epilogue/?p=186

Cheers,
-- Dan
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
12