Applicative but not Monad

newer
Lecture Notes Advanced Functional...

older
ANN: BlogLiterately-0.2

Yusaku Hashimoto

30 Oct 2009 30 Oct '09

12:14 p.m.

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

Show replies by date

Eugene Kirpichov

30 Oct 30 Oct

12:25 p.m.

Yes. ZipList. http://en.wikibooks.org/wiki/Haskell/Applicative_Functors 2009/10/30 Yusaku Hashimoto :

...

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

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

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

Tom Davie

12:39 p.m.

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

...

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

2009/10/30 Yusaku Hashimoto :

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

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

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

Luke Palmer

12:59 p.m.

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

Tom Davie

1:06 p.m.

On Fri, Oct 30, 2009 at 5:59 PM, Luke Palmer wrote:

...

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

Yusaku Hashimoto

1:33 p.m.

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

...

On Fri, Oct 30, 2009 at 5:59 PM, Luke Palmer wrote:

...
On Fri, Oct 30, 2009 at 10:39 AM, 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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

David Menendez

1:39 p.m.

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

Yusaku Hashimoto

1:57 p.m.

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

...

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

Job Vranish

5:06 p.m.

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

...
On Fri, Oct 30, 2009 at 5:59 PM, Luke Palmer wrote:

...
On Fri, Oct 30, 2009 at 10:39 AM, 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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

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

David Menendez

1:32 p.m.

On Fri, Oct 30, 2009 at 12:59 PM, Luke Palmer wrote:

...

On Fri, Oct 30, 2009 at 10:39 AM, 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 http://www.eyrie.org/~zednenem/

Dan Weston

2:48 p.m.

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 mailto:ekirpichov@gmail.com> wrote:

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

2009/10/30 Yusaku Hashimoto mailto:nonowarn@gmail.com>: > Hello cafe, > Do you know any data-type which is Applicative but not Monad? > > Cheers, > -~nwn > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org mailto:Haskell-Cafe@haskell.org > 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@haskell.org mailto:Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Miguel Mitrofanov

2:52 p.m.

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

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

Heinrich Apfelmus

31 Oct 31 Oct

6:22 a.m.

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

Tom Davie

7:25 a.m.

On 10/31/09, Heinrich 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

Daniel Fischer

7:51 a.m.

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

...

On 10/31/09, Heinrich 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)

David Menendez

11:38 a.m.

On Sat, Oct 31, 2009 at 6:22 AM, Heinrich Apfelmus 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 http://www.eyrie.org/~zednenem/

Ryan Ingram

3:26 p.m.

On Sat, Oct 31, 2009 at 8:38 AM, David Menendez wrote:

...

On Sat, Oct 31, 2009 at 6:22 AM, Heinrich Apfelmus 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 []

Martijn van Steenbergen

30 Oct 30 Oct

4:35 p.m.

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.

Yusaku Hashimoto

6:17 p.m.

...

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

Jeremy Shaw

4:51 p.m.

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

Tony Morris

6:18 p.m.

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

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

Conor McBride

31 Oct 31 Oct

6:39 a.m.

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

Conor McBride

1 Nov 1 Nov

11:20 a.m.

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

David Menendez

5:23 p.m.

On Sun, Nov 1, 2009 at 11:20 AM, Conor McBride 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 http://www.eyrie.org/~zednenem/

Ross Paterson

7:11 p.m.

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

Conor McBride

7:17 p.m.

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

Dan Weston

2 Nov 2 Nov

2:56 p.m.

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

Dan Doel

3 Nov 3 Nov

12:39 a.m.

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