William Lee Irwin III writes:
>> [...]
>> The rationals may be enumerated according to the construction given
>> by Cantor, or by various other means.
On Tue, Jul 11, 2000 at 12:15:24PM +1200, Tom Pledger wrote:
> There was a related discussion last year, starting from this point in
> the archive:
> http://www.mail-archive.com/haskell@haskell.org/msg04117.html
> Regards,
> Tom Pledger
It should, in principle, be possible to do this for all countable types.
Any surjection from a subset of the naturals onto the underlying set of
a type will induce an ordering. Doubtless I am preaching to the choir.
Perhaps a more interesting point to consider is that with nonstrict
semantics lists over denumerable types are not denumerable, but with
strict semantics they are; likewise with general trees. The
implications of deriving Enum for such things are unclear; it would
be impossible to successfully enumerate all the elements of the
nondenumerable types, and any attempt to do so would produce incorrect
results.
So in an algebraic data type like the one you demonstrated, one might
have to be careful about ensuring that the type is not recursive; but
I'm not sure whether anyone would want to make this sort of distinction
in deciding whether a given type could derive Enum, though it's likely
feasible.
Sergey Mechveliani brings up another point, where the enumerations are
not faithful to the natural orderings in product types (and possibly
others). This is probably a strong argument against deriving Enum willy
nilly for various kinds of types. On the other hand, one often doesn't
care if the enumeration is faithful so long as it enumerates all
possible things. This is a common enough case perhaps it deserves some
mention in libraries. Also, note that in the case of finite domains,
product types may be naturally ordered as usual, e.g.
{- Assuming a class Finite in case Bounded doesn't imply enough. -}
instance (Enum a, Enum b, Finite b) => Enum (a,b) where
succ (x,y) = {- if y is the top of b, then (succ x, bottom b)
else (x, succ y) -}
pred (x, y) = {- if y is the bottom of b, then pred x, top b)
else (x, pred y) -}
etc.
in more general product types, instances of Finite would be required
for all positions in the n-tuple but the first, etc.
I didn't see these issues arise in the prior discussion, so I'm going
to post this reply back to the list. I hope it wasn't because they
were too obvious to mention.
Cheers,
Bill
