Monad for Pair

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
14 messages Options
Reply | Threaded
Open this post in threaded view
|

Monad for Pair

Mike Houghton
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
Reply | Threaded
Open this post in threaded view
|

Re: Monad for Pair

Marcin Mrotek
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
Reply | Threaded
Open this post in threaded view
|

Re: Monad for Pair

Kim-Ee Yeoh
Administrator
In reply to this post by Mike Houghton

On Wed, Nov 18, 2015 at 4:41 AM, Mike Houghton <[hidden email]> 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
Reply | Threaded
Open this post in threaded view
|

Re: Monad for Pair

Kim-Ee Yeoh
Administrator
In reply to this post by Marcin Mrotek

On Wed, Nov 18, 2015 at 5:15 AM, Marcin Mrotek <[hidden email]> 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
Reply | Threaded
Open this post in threaded view
|

Re: Monad for Pair

Marcin Mrotek
> 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
Reply | Threaded
Open this post in threaded view
|

Re: Monad for Pair

Kim-Ee Yeoh
Administrator

On Wed, Nov 18, 2015 at 3:28 PM, Marcin Mrotek <[hidden email]> 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
Reply | Threaded
Open this post in threaded view
|

Re: Monad for Pair

Gesh
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/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/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Monad for Pair

Marcin Mrotek
> 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
Reply | Threaded
Open this post in threaded view
|

Re: Monad for Pair

Mike Houghton
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

Mike

On 18 Nov 2015, at 07:23, Kim-Ee Yeoh <[hidden email]> wrote:


On Wed, Nov 18, 2015 at 4:41 AM, Mike Houghton <[hidden email]> 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
Reply | Threaded
Open this post in threaded view
|

Re: Monad for Pair

Mike Houghton
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

Mike

On 18 Nov 2015, at 07:23, Kim-Ee Yeoh <[hidden email]> wrote:


On Wed, Nov 18, 2015 at 4:41 AM, Mike Houghton <[hidden email]> 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
Reply | Threaded
Open this post in threaded view
|

Re: Monad for Pair

Kim-Ee Yeoh
Administrator
In reply to this post by Mike Houghton

On Thu, Nov 19, 2015 at 1:33 AM, Mike Houghton <[hidden email]> 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
Reply | Threaded
Open this post in threaded view
|

Re: Monad for Pair

Mike Houghton
"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



On 19 Nov 2015, at 06:34, Kim-Ee Yeoh <[hidden email]> wrote:


On Thu, Nov 19, 2015 at 1:33 AM, Mike Houghton <[hidden email]> 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
Reply | Threaded
Open this post in threaded view
|

Re: Monad for Pair

Mike Houghton
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 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

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Monad for Pair

Marcin Mrotek
> 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 pseudo-Haskell, 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/cgi-bin/mailman/listinfo/beginners