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 |
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 |
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. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
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 |
On Fri, Oct 30, 2009 at 5:59 PM, Luke Palmer <[hidden email]> wrote:
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
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 |
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 |
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 |
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 |
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 |
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 |
Free forum by Nabble | Edit this page |