Haskell Typeclass – Why Isn’t Bounded a Subclass of Enum in Haskell?

haskelltypeclass

It seems like any Bounded instance should have a sane implementation of Enum. I cannot personally think of a counterexample, although if someone comes up with one that isn't pathological then I will understand why this isn't the case.

From doing :i on the two typeclasses it seems like the only exception currently in the standard library is for tuples, which are Bounded but not Enums. However any Bounded tuple must also be Enumerable in a sane way, by simply incrementing the last element and then wrapping around when it gets to maxBound.

This change would probably also involve adding predB and nextB or something like that to Bounded for a safe/looping way to traverse through the Enum values. In this case toEnum 0 :: (...) would be equal to (toEnum 0, toEnum 0, ...) :: (...)

Best Answer

One practical example I like comes from the world of programming languages: the set of types in an OO system is bounded and discrete but not enumerable, and partially ordered but not totally ordered.

The partial ordering in question is the subtyping relation <:. The upper bound would then be the top type (which C# calls object and Scala calls Any), and the lower bound would be the bottom type (Scala's Nothing; C#/Java have no equivalent to speak of).

However, there is no way to enumerate all the types in the type system, so you can't write an instance Enum Type. After all, users can write their own types so there's no way to know what they'll be in advance. You can enumerate all the types in any given program, but not in the whole system.

Likewise, (according to a certain reasonable definition of subtyping,) <: is reflexive, transitive and antisymmetric but not total. There are pairs of types which are unrelated by <:. (Cat and Dog are both subtypes of Animal, but neither is a subtype of the other.)

Suppose that we're writing a compiler for a simple OO language. Here's the representation of types in our system:

data Type = Bottom | Class { name :: String, parent :: Type } | Top

And the definition of the subtyping relation:

(<:) :: Type -> Type -> Bool
Bottom <: _ = True
Class _ _ <: Bottom = False
Class n t <: s@(Class m _)
    | n == m = True  -- you can't have different classes with the same name in this hypothetical language
    | otherwise = t <: s  -- try to find s in the parents of this class
Class _ _ <: Top = True
Top <: Top = True
Top <: _ = False

This also gives us a supertyping relation.

(>:) :: Type -> Type -> Bool
t >: s = s <: t

You can also find the least upper bound of two types,

lub :: Type -> Type -> Type
lub Bottom s = s
lub t Bottom = t
lub t@(Class _ p) s@(Class _ q) =
    | t >: s = t
    | t <: s = s
    | p >: s = p
    | t <: q = q
    | otherwise = lub p q
lub Top _ = Top
lub _ Top = Top

Exercise: show that Type forms a bounded complete poset two ways, under <: and under >:.

Related Topic