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