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

[Daniel Fischer]

On Friday 04 March 2011 17:45:13, Markus Läll wrote:
> Sorry, I didn't mean to answer you in particular. I meant to say that
> for tuples you could (I think) have an enumeration over them without
> requiring any component be bounded.

Yes, you can (at least mathematically, it may be different if you consider 
actual Enum instances, then Int overflow has to be reckoned with).

The problem is with simultaneous Ord and Enum instances.
Let's call an

instance Ord A where ...

and an

instance Enum A where ...

compatible when toEnum and fromEnum are strictly monotonic, i.e.

x `rel` y <=> fromEnum x `rel` fromEnum y

for rel in { (<), (==), (>) }
and analogously for toEnum (restricted to legitimate arguments).
And let's ignore overflow, so pretend Int were infinite (so Int = Z).

That means, for compatible Ord and Enum instances, it follows that for any 
x, y \in A with x <= y, the set { z \in A : x <= z && z <= y } is finite 
[it has at most (fromEnum y - fromEnum x + 1) elements].

So when A is a tuple type and the Ord instance is lexicographic ordering,
a compatible Enum instance is only possible if

- at least one component is empty, or
- at most one component is infinite and only single-element types appear as 
components before the infinite one.

Otherwise, if x1 < x2 and Y is infinite, the set
S(t) = { (x,y) : (x1,t) <= (x,y) && (x,y) <= (x2,t) }
is infinite because we can embed Y into it [foo y = if y < t then (x2,y) 
else (x1,y)].

In fact, for any Enum instance, there is exactly one compatible Ord 
instance, namely

x `rel` y <=> fromEnum x `rel` fromEnum y

Conversely, given an Ord instance, if there exists a compatible Enum 
instance, fromEnum gives an order-isomorphism between A and a subset of the 
integers. Then there are four main possibilities

1. A is finite
(then A has the order type of some natural number n = card(A))
2. A has a smallest element but not a largest
(then A has the order type of the natural numbers N)
3. A has a largest element but no smallest
(then A has the order type of Z-N)
4. A has neither a smallest nor a largest element
(then A has the order type of Z)

Anyway, there exists a compatible Enum instance (and then infinitely many), 
if and only if A has the order type of a subset of the integers.

> 
> An example of type (Integer, Integer) you would have:
> 
> [(0,0) ..] = [(0,0) (0,1) (1,0) (0,2) (1,1) (2,0) ... ]

That's (Nat, Nat) rather than (Integer,Integer), not fundamentally 
different, but simpler to handle.

> 
> where the order can be visualized by taking diagonals of a table
> starting from the upper left:
> 
>     0      1      2     ..
> 0 (0,0)  (0,1)  (0,2)
> 1 (1,0)  (1,1)  (1,2)
> 2 (2,0)  (2,1)  (2,2)
> ..
> 
> Would this also have an uncomputable order type?

No, order type is that of N, if order is given by enumeration

> At least for comparing
> tuples you'd just:
> 
> lt :: (Integer,Integer) -> (Integer,Integer) -> Bool
> (a,b) `lt` (c,d) = let
>       sum1 = (a + b)
>       sum2 = (c + d)
>    in if sum1 == sum2
>          then a < c
>          else sum1 < sum2
> 
> 
> Implementing fromEnum looks like a bit harder problem..

That's pretty easy, in fact.

fromEnum (a,b) = t + a
  where
    s = a+b
    t = (s*(s+1)) `quot` 2 -- triangular number

toEnum is a bit more difficult, you have to take a square root to see on 
which diagonal you are