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

Thanks for this - I’ll work through it. Mike

On 18 Nov 2015, at 08:28, Marcin Mrotek wrote:

...

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 Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

On November 18, 2015 12:15:37 AM GMT+02:00, Marcin Mrotek 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 Beginners@haskell.org http://mail.haskell.org/cgi-bin/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

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

'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

On 18 Nov 2015, at 07:23, Kim-Ee Yeoh mailto:ky3@atamo.com> wrote:

On Wed, Nov 18, 2015 at 4:41 AM, Mike Houghton mailto:mike_k_houghton@yahoo.co.uk> 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 Beginners@haskell.org mailto:Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners