14 messages
Open this post in threaded view
|

 Hi, I have newtype Pair a = P (a, a) deriving (Show) and have made Monoid, Applicative and Functor instances for it. I’m a bit stumped with Monad! instance Monad Pair where   return x  = P (x, x) and I got brain ache with >>= And really return x  = P (x, x)   doesn’t seem correct anyway. Would someone please write the Monad with an explanation? Many Thanks Mike _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Open this post in threaded view
|

 Hello, I'm pretty sure a Pair (like any other fixed-length type, besides the corner case of a single field like in Writer, Identity, etc) can't be a monad. Perhaps instead of struggling with >>=, consider join. It has a type: join :: Monad m => m (m a) -> m a for Pairs that would be join :: Pair (Pair a) -> Pair a join (Pair (Pair a1 a2) (Pair b1 b2)) = Pair _ _ How do you want to fit four values into two boxes? You cannot place any constraints on the type inside the pair, so it can't be a monoid or anything that would let you combine the values somehow. You could only choose two of the values and drop the other two on the floor. Getting back to >>=, it's assumed to follow these laws: 1) return a >>= k  =  k a 2) m >>= return    =  m 3) m >>= (\x -> k x >>= h)  =  (m >>= k) >>= h As for the firs, return a = Pair a a. Then the first two laws become 1) Pair a a >>= k = k a 2) Pair a b >>= (\a -> Pair a a) = Pair a b The first law could work if >>= just chose one of the values arbitrarily. But the second law is a hopeless case. You would need to pick one element of a pair, plug it into a function that repeats the argument, and somehow get back the other element that you've already dropped. Concluding, either I'm sorely mistaken or there indeed isn't a Monad instance for Pair. Best regards, Marcin Mrotek _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Open this post in threaded view
|

 Administrator In reply to this post by Mike Houghton On Wed, Nov 18, 2015 at 4:41 AM, Mike Houghton wrote: And really return x  = P (x, x) doesn’t seem correct anyway.But if you look at the type, which is essentially "a -> (a,a)" there's only one way to write it, for the same reason that there's only one "a -> a" function. Would someone please write the Monad with an explanation?Much better if you let us know the source of this problem. Is this an exercise from some book / online course?-- Kim-Ee _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Open this post in threaded view
|

 Administrator In reply to this post by Marcin Mrotek On Wed, Nov 18, 2015 at 5:15 AM, Marcin Mrotek wrote: The first law could work if >>= just chose one of the values arbitrarily. But the second law is a hopeless case. You would need to pick one element of a pair, plug it into a function that repeats the argument, and somehow get back the other element that you've already dropped. Concluding, either I'm sorely mistaken or there indeed isn't a Monad instance for Pair.Not quite sorely mistaken but there is a glitch in the logic of what you wrote when you returned from join to bind.You might want to try writing out a test instance in full and re-checking the second law.-- Kim-Ee _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Open this post in threaded view
|

 > You might want to try writing out a test instance in full and re-checking the second law. Ok, while the part upto Applicative is correct and unambiguous: data Pair a = Pair a a instance Functor Pair where   fmap f (Pair a b) = Pair (f a) (f b) instance Applicative Pair where   pure a = Pair a a   Pair fa fb <*> Pair a b = Pair (fa a) (fb b) there are at least two implementations of Monad (assuming return=pure, also GHC 7.10 allows omitting return and implements it exactly like that): -- implementation (a) instance Monad Pair where   Pair a _ >>= k = k a -- implementation (b) instance Monad Pair where   Pair _ b >>= k = k b ... neither of which can satisfy the laws. There are more: -- implementation (c) instance Monad Pair where   Pair a b >>= k = Pair a' b'     where       Pair a' _ = k a       Pair _ b' = k b -- implementation (d) instance Monad Pair where   Pair a b >>= k = Pair a' b'     where       Pair _ b' = k a       Pair a' _ = k b and, well: instance Monad Pair where   Pair a b >>= _ = Pair a b Did I miss anything? Now, trying to get the second law to work: a) m >>= return = m Pair a b >>= (\a -> Pair a a) = Pair a b Pair a a = Pair a b contradiction. b) m >>= return = m Pair a b >>= (\a -> Pair a a) = Pair a b Pair b b = Pair a b contradiction. c) m >>= return = m Pair a b >>= (\a -> Pair a a) = Pair a b Pair a b = Pair a b no contradiction this time, I'll write the other laws after I'm done with the second for the other instances. d) m >>= return = m Pair a b >>= (\a -> Pair a a) = Pair a b Pair b a = Pair a b contradiction. e) m >>= return = m trivially correct. Testing the first law for (c) and (e) that passed the second law: c) return a >>= k = k a Pair a a >>= k a = k a --- Pair a' b' = k a   where     Pair a' _ = k a     Pair _ b' = k a --- no contradiction again. e) return a >>= k = k a return a = k a contradiction. Okay, then testing the third law for (c): m >>= (\x -> k x >>= h)  =  (m >>= k) >>= h Pair a b >>=  (\x -> k x >>= h) = (Pair a b >>= k) >>= h (*) Let's again unpack the application of >>= in some pseud-haskell: Pair a1 _ = (\x -> k x >>= h) a = k a >>= h (**) Pair _ b1 = (\x -> k x >>= h) b = k b >> =h Pair a2 _ = k a (***) Pair _ b2 = k b plugging it into (*): Pair a1 b1 = Pair a2 b2 >>= h Unpacking >>= again: Pair a3 _ = h a2 (****) Pair _ b3 = h b2 Pair a1 b1 = Pair a3 b3 Now, testing if a1 = a3, lets bring in (**), (***), and (****): Pair a1 _ = k a >>= h Pair a2 _ = k a Pair a3 _ = h a2 Form the first and the second equations (also using the one for b2 earlier, but it's going to be dropped anyway sooner or later) we get: Pair a1 _ = Pair a2 b2 >>= h Unpacking >>= : Pair a4 _ = h a2 Pair _ b4 = h b2 But from the third equation we know that (Pair a3 _ = h a2) so: Pair a1 _ = Pair a3 _ This does seem to work, I have no idea why. I'm pretty sure there I've made a mistake somewhere. Perhaps I shouldn't do equational reasoning after just getting up, or just use Agda :-/ Best regards, Marcin Mrotek _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Open this post in threaded view
|

 Administrator On Wed, Nov 18, 2015 at 3:28 PM, Marcin Mrotek wrote:This does seem to work, I have no idea why. I'm pretty sure there I've made a mistake somewhere. Perhaps I shouldn't do equational reasoning after just getting up, or just use Agda :-/Congrats ! Vuvuzela !If there are bugs in the proof, you can give it to your students to patch up.-- Kim-Ee _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Open this post in threaded view
|

 In reply to this post by Marcin Mrotek On November 18, 2015 12:15:37 AM GMT+02:00, Marcin Mrotek <[hidden email]> wrote: >Hello, > >I'm pretty sure a Pair (like any other fixed-length type, besides the >corner case of a single field like in Writer, Identity, etc) can't be >a monad. Perhaps instead of struggling with >>=, consider join. It has >a type: > >join :: Monad m => m (m a) -> m a > >for Pairs that would be > >join :: Pair (Pair a) -> Pair a >join (Pair (Pair a1 a2) (Pair b1 b2)) = Pair _ _ > >How do you want to fit four values into two boxes? You cannot place >any constraints on the type inside the pair, so it can't be a monoid >or anything that would let you combine the values somehow. You could >only choose two of the values and drop the other two on the floor. > >Getting back to >>=, it's assumed to follow these laws: > >1) return a >>= k  =  k a >2) m >>= return    =  m >3) m >>= (\x -> k x >>= h)  =  (m >>= k) >>= h > >As for the firs, return a = Pair a a. Then the first two laws become > >1) Pair a a >>= k = k a >2) Pair a b >>= (\a -> Pair a a) = Pair a b > >The first law could work if >>= just chose one of the values >arbitrarily. But the second law is a hopeless case. You would need to >pick one element of a pair, plug it into a function that repeats the >argument, and somehow get back the other element that you've already >dropped. > >Concluding, either I'm sorely mistaken or there indeed isn't a Monad >instance for Pair. > >Best regards, >Marcin Mrotek >_______________________________________________ >Beginners mailing list >[hidden email] >http://mail.haskell.org/cgi-bin/mailman/listinfo/beginnersNo. Pair can be made into a monad, and this is made clear by realizing that Pair a ~ Bool -> a, so the monad instance for Reader should work here. In fact, this means that any representable functor (i.e. f s.t. f a ~ t-> a for some t) has all instances that Reader r has for fixed r. HTH, Gesh _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Open this post in threaded view
|

 > If there are bugs in the proof, you can give it to your students to patch up. If I'll ever have any, they aren't going to be CS students :) > Pair a ~ Bool -> a, so the monad instance for Reader should work here Okay, that makes sense. Sorry for the noise then. Best regards, Marcin Mrotek _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Open this post in threaded view
|

 In reply to this post by Kim-Ee Yeoh 'Much better if you let us know the source of this problem. Is this an exercise from some book / online course?”The source is just me exploring. I first looked at data C a = C a deriving (Show)and made Monad, Applicative, Monoid and Functors for it.So then tried Pair a = P (a, a)  and stuck on Monad.Thanks MikeOn 18 Nov 2015, at 07:23, Kim-Ee Yeoh <[hidden email]> wrote:On Wed, Nov 18, 2015 at 4:41 AM, Mike Houghton wrote: And really return x  = P (x, x) doesn’t seem correct anyway.But if you look at the type, which is essentially "a -> (a,a)" there's only one way to write it, for the same reason that there's only one "a -> a" function. Would someone please write the Monad with an explanation?Much better if you let us know the source of this problem. Is this an exercise from some book / online course?-- Kim-Ee _______________________________________________Beginners mailing list[hidden email]http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners_______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Open this post in threaded view
|

 In reply to this post by Kim-Ee Yeoh 'Much better if you let us know the source of this problem. Is this an exercise from some book / online course?”The source is just me exploring. I first looked at data C a = C a deriving (Show)and made Monad, Applicative, Monoid and Functors for it.So then tried Pair a = P (a, a)  and stuck on Monad.Thanks MikeOn 18 Nov 2015, at 07:23, Kim-Ee Yeoh <[hidden email]> wrote:On Wed, Nov 18, 2015 at 4:41 AM, Mike Houghton wrote: And really return x  = P (x, x) doesn’t seem correct anyway.But if you look at the type, which is essentially "a -> (a,a)" there's only one way to write it, for the same reason that there's only one "a -> a" function. Would someone please write the Monad with an explanation?Much better if you let us know the source of this problem. Is this an exercise from some book / online course?-- Kim-Ee _______________________________________________Beginners mailing list[hidden email]http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners_______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Open this post in threaded view
|

 Administrator In reply to this post by Mike Houghton On Thu, Nov 19, 2015 at 1:33 AM, Mike Houghton wrote:The source is just me exploring. Nice. I first looked at data C a = C a deriving (Show)and made Monad, Applicative, Monoid and Functors for it.Even though the null-effect instances for the identity functor are trivial, there's value in writing them out, especially for the motivated.But how do you take an arbitrary type and turn it into a monoid?-- Kim-Ee _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Open this post in threaded view
|

 "But how do you take an arbitrary type and turn it into a monoid?”I didn’t -  I must have been dreaming about Haskell at that point :)   (My wife once dreamt she was a C compiler - go figure… C !!??) No, just Monad, Applicative and Functor - my mistake.Thanks MikeOn 19 Nov 2015, at 06:34, Kim-Ee Yeoh <[hidden email]> wrote:On Thu, Nov 19, 2015 at 1:33 AM, Mike Houghton wrote:The source is just me exploring. Nice. I first looked at data C a = C a deriving (Show)and made Monad, Applicative, Monoid and Functors for it.Even though the null-effect instances for the identity functor are trivial, there's value in writing them out, especially for the motivated.But how do you take an arbitrary type and turn it into a monoid?-- Kim-Ee _______________________________________________Beginners mailing list[hidden email]http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners_______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners