[Haskell-cafe] Learn You a Haskell for Great Good - a few doubts

[Richard O'Keefe]

On 4/03/2011, at 10:47 PM, Karthick Gururaj wrote:

> On Fri, Mar 4, 2011 at 10:42 AM, Richard O'Keefe <ok at cs.otago.ac.nz> wrote:
>> 
>> On 4/03/2011, at 5:49 PM, Karthick Gururaj wrote:
>>> I meant: there is no reasonable way of ordering tuples, let alone enum
>>> them.
>> 
>> There are several reasonable ways to order tuples.
>>> 
>>> That does not mean we can't define them:
>>> 1. (a,b) > (c,d) if a>c
>> 
>> Not really reasonable because it isn't compatible with equality.
>>> 2. (a,b) > (c,d) if b>d
>>> 3. (a,b) > (c,d) if a^2 + b^2 > c^2 + d^2
>>> 4. (a,b) > (c,d) if a*b > c*d
>> 
>> Ord has to be compatible with Eq, and none of these are.
> Hmm.. not true. Can you explain what do you mean by "compatibility"?

Trichotomy.
Ad definition 1:
	(1,2) > (1,3) is false
	(1,2) > (1,3) is false
but	(1,2) ==(1,3) is also false.

Ad definition 2:
	Same as definition 1 only flipped.

Ad definition 3:
	(3,4) > (4,3) is false
	(3,4) < (4,3) is false
but	(3,4) ==(4,3) is also false.

Ad definition 4:

	(1,0) > (0,1) is false
	(1,0) < (0,1) is false
but	(1,0) ==(0,1) is also false.

Ord is a subclass of Eq, after all.
> 
> One of the following, and exactly one, must always hold, on a ordered
> set (is this what you mean by "compatibility"?), for any arbitrary
> legal selection of a, b, c and d.
> a. (a, b) EQ (c, d)
> b. (a, b) LT (c, d)
> c. (a, b) GT (c, d)
> 
> All the definitions above are compatible in this sense.

As I just showed, none of them is.
>>> As a side note, the cardinality of rational numbers is the same as
>>> those of integers - so both are "equally" infinite.
>> 
>> Ah, here we come across the distinction between cardinals and
>> ordinals.  Two sets can have the same cardinality but not be
>> the same order type.  (Add 1 to the first infinite cardinal
>> and you get the same cardinal back; add 1 to the first infinite
>> ordinal and you don't get the same ordinal back.)
> 
> :) Ok. The original point was whether there is a reasonable way to
> enumerate a tuple, I guess there is none.

And the original point was about ordering, which is why it's
relevant that there are more order types than size types.