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

[Karthick Gururaj]

On Mon, Mar 7, 2011 at 6:12 AM, Richard O'Keefe <ok at cs.otago.ac.nz> wrote:
>
> 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.

My definitions were incomplete, they need to be "extended" and not
taken as is. Let me define them completely for the sake of this
argument:
Defn 1. Given four arbitrary a, b, c and d on a set X which is an
instance of Ord (so a = b, a > b and a < b are defined), let:
   (a, b) > (c, d) iff a > c  (GT)
   (a, b) < (c, d) iff a < c  (LT)
   (a, b) = (c, d) iff a = c. (EQ)
(please note that I'm redefining the EQ for pairs as well).

With this, the following hold:
   (1, 2) = (1, 3)
   (2, 1) > (1, 10)
   (4, 0) < (5, 5)
It should be obvious that only one of GT, LT and EQ will hold, for any
arbitrary a, b, c, d.

Of course, the definition of EQ here is not what would be considered
"reasonable". I also see now, as I'm typing this, if we define EQ to
be the way it is in Haskell (which IS the reasonable way), then none
of my definitions of GT/LT will hold. Also, using the lexical compare
DOES fall in place with the EQ the way it is defined..

The confusion started for me as I thought of n-tuples as vectors in
n-dimensional space, on which one doesn't usually define GT and LT
operators. Now I see some light :)

>>
>> 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.
>
>