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/cgibin/mailman/listinfo/beginners 
Hello,
I'm pretty sure a Pair (like any other fixedlength 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/cgibin/mailman/listinfo/beginners 
Administrator

In reply to this post by Mike Houghton
On Wed, Nov 18, 2015 at 4:41 AM, Mike Houghton <[hidden email]> wrote:
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.
Much better if you let us know the source of this problem. Is this an exercise from some book / online course?  KimEe _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgibin/mailman/listinfo/beginners 
Administrator

In reply to this post by Marcin Mrotek
On Wed, Nov 18, 2015 at 5:15 AM, Marcin Mrotek <[hidden email]> wrote:
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 rechecking the second law.  KimEe _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgibin/mailman/listinfo/beginners 
> You might want to try writing out a test instance in full and rechecking 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 pseudhaskell: 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/cgibin/mailman/listinfo/beginners 
Administrator

On Wed, Nov 18, 2015 at 3:28 PM, Marcin Mrotek <[hidden email]> wrote:
Congrats ! Vuvuzela ! If there are bugs in the proof, you can give it to your students to patch up. KimEe _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgibin/mailman/listinfo/beginners 
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 fixedlength 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/cgibin/mailman/listinfo/beginners No. 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/cgibin/mailman/listinfo/beginners 
> 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/cgibin/mailman/listinfo/beginners 
In reply to this post by KimEe 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 Mike
_______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgibin/mailman/listinfo/beginners 
In reply to this post by KimEe 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 Mike
_______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgibin/mailman/listinfo/beginners 
Administrator

In reply to this post by Mike Houghton
On Thu, Nov 19, 2015 at 1:33 AM, Mike Houghton <[hidden email]> wrote:
Nice.
Even though the nulleffect 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?  KimEe _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgibin/mailman/listinfo/beginners 
"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 Mike
_______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgibin/mailman/listinfo/beginners 
In reply to this post by Marcin Mrotek
Thanks for this  I’ll work through it.
Mike > On 18 Nov 2015, at 08:28, Marcin Mrotek <[hidden email]> wrote: > >> You might want to try writing out a test instance in full and rechecking 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 pseudhaskell: > > 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/cgibin/mailman/listinfo/beginners _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgibin/mailman/listinfo/beginners 
> Thanks for this  I’ll work through it.
Yeah, apparently I accidentaly wrote a correct instance there. You can also use what Gesh wrote, and try to derive an instance from something like: tabulate :: (Bool > a) > Pair a tabulate f = Pair (f True) (f False) index :: Pair a > Bool > a index (Pair a _) True = a index (Pair _ b) False = b instance Applicative Pair where pure = tabulate . pure fp <*> fa = tabulate $ index fp <*> index fa instance Monad Pair where m >>= f = tabulate $ index m >>= index . f The instances for a function are (in pseudoHaskell, I don't think GHC accepts (a >) instead of ((>) a), but it looks cleaner that way) instance Applicative (a >) where pure = const f <*> g = \x > f x (g x) instance Monad (a >) where f >>= k = \ r > k (f r) r > My wife once dreamt she was a C compiler  go figure… C !!?? C isn't exactly known for type safety, so things can indeed get Kafkaesque sometimes. Best regards, Marcin Mrotek _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgibin/mailman/listinfo/beginners 
Free forum by Nabble  Edit this page 