Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Monad for Pair (Mike Houghton)
2. Re: Monad for Pair (Marcin Mrotek)
3. Re: Monad for Pair (Kim-Ee Yeoh)
4. Re: Monad for Pair (Kim-Ee Yeoh)
5. Re: Monad for Pair (Marcin Mrotek)
6. Re: Monad for Pair (Kim-Ee Yeoh)
7. Re: Monad for Pair (Gesh)
----------------------------------------------------------------------
Message: 1
Date: Tue, 17 Nov 2015 21:41:20 +0000
From: Mike Houghton <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: [Haskell-beginners] Monad for Pair
Message-ID: <[email protected]>
Content-Type: text/plain; charset=utf-8
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
------------------------------
Message: 2
Date: Tue, 17 Nov 2015 23:15:37 +0100
From: Marcin Mrotek <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Monad for Pair
Message-ID:
<CAJcfPzk8H51FarLniwJug=63xpzh+basrgg5s99fekgvxli...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
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
------------------------------
Message: 3
Date: Wed, 18 Nov 2015 14:23:37 +0700
From: Kim-Ee Yeoh <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Monad for Pair
Message-ID:
<CAPY+ZdRY9kZv9igFMSQXphC=eiz9sefnt7vcx-dsm+afvzd...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
On Wed, Nov 18, 2015 at 4:41 AM, Mike Houghton <[email protected]>
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20151118/f959b841/attachment-0001.html>
------------------------------
Message: 4
Date: Wed, 18 Nov 2015 14:44:56 +0700
From: Kim-Ee Yeoh <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Monad for Pair
Message-ID:
<CAPY+ZdRx3aH+z0F6L5sc_ptZK22n4UuR7otzrw9=dok+wjo...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
On Wed, Nov 18, 2015 at 5:15 AM, Marcin Mrotek <[email protected]>
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20151118/a9d829fb/attachment-0001.html>
------------------------------
Message: 5
Date: Wed, 18 Nov 2015 09:28:22 +0100
From: Marcin Mrotek <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Monad for Pair
Message-ID:
<CAJcfPzkXbBhQZFTpbM6Cne4Ssk+5K=mnxn4pp3cqb5qzmg6...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
> 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
------------------------------
Message: 6
Date: Wed, 18 Nov 2015 15:44:11 +0700
From: Kim-Ee Yeoh <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Monad for Pair
Message-ID:
<CAPY+ZdTFjYnCOujJZrO1+U0Bwi=5sbx_fbu5jeej6fkxjo8...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
On Wed, Nov 18, 2015 at 3:28 PM, Marcin Mrotek <[email protected]>
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20151118/c948a6bb/attachment-0001.html>
------------------------------
Message: 7
Date: Wed, 18 Nov 2015 10:59:10 +0200
From: Gesh <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Monad for Pair
Message-ID: <[email protected]>
Content-Type: text/plain; charset=UTF-8
On November 18, 2015 12:15:37 AM GMT+02:00, Marcin Mrotek
<[email protected]> 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
>[email protected]
>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
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 89, Issue 30
*****************************************
