6

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, ...) :: (...)

  • 2
    Can't really answer this authoritatively but consider the range of all real numbers between 0 and 1. It has clear lower and upper bounds but it has uncountably infinite members. – Doval Mar 29 '16 at 23:40
  • @Doval that is a fair point. However the same could be said about all real numbers in general (uncountably infinite members), but Double / Float and all similar types implement Enum anyway, they just make succ = (+ 1) and fromEnum = truncate. Haskell's way does actually make sense from a practicality perspective as otherwise [0, 0.5..] and similar wouldn't work, so it seems Haskell does not worry about countability when it comes to Enums. – semicolon Mar 30 '16 at 1:31
  • 1
    I wasn't aware that succ is (+1). That's strange, because Double and Float do not have infinite precision and thus are enumerable - succ could've been defined to be +1 ULP. – Doval Mar 30 '16 at 2:46
  • 1
    @Doval I think the reason for that was because the Haskell core team wanted [1..] to mean the same thing with Doubles that it means with Ints. – semicolon Mar 30 '16 at 4:35
  • @semicolon doubles and floats are not Real numbers (e.g. can not store PI in a double without losing some precision) so they are enumerable – jk. Mar 31 '16 at 8:26
6

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. This should be clear: 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 >:.

  • Awesome thanks! That answers my question completely and also answers my follow up question about Ord. Would Eq have similar issues? Where a non-equatable type might have a maxBound or a minBound. In this case should Cat == Dog just return false, as they are different classes, or would it be undecidable because of the tree position puts neither above or below the other? – semicolon Mar 30 '16 at 17:51
  • An ordering implies an equality - just define x == y = x <= y && y <= x. If I were designing a Poset class I'd have class Eq a => Poset a. A quick Google confirms that other people have had the same idea. – Benjamin Hodgson Mar 30 '16 at 18:15
  • Sorry my question was ambiguous. What I meant was whether Bounded implied Eq even if it doesn't imply Ord. – semicolon Mar 30 '16 at 19:03
  • @semicolon Again there's no relationship between the two classes. Consider data Bound a = Min | Val a | Max which augments a type a with +∞ and -∞ elements. By construction Bound a can always be made an instance of Bounded but it'd only be equatable if the underlying type a is – Benjamin Hodgson Apr 13 '16 at 23:14
  • alright fair enough. I guess one example could be functions that take and return values of type Double, where const (1/0) is maxBound and const (negate 1/0) is minBound but \x -> 1 - x and \x -> x - 1 are incomparable. – semicolon Apr 13 '16 at 23:29
3

It's because the operations are independent, so tying them together with a subclass relationship doesn't actually buy you anything. Say you wanted to create a custom type that implemented Bounded, perhaps Doubles constrained between a max and min, but you had no need for any of the Enum operations. If Bounded were a subclass, you would have to implement all the Enum functions anyway, just to get it to compile.

It doesn't really matter if there's a reasonable implementation for Enum, or any other number of typeclasses. If you don't actually need it, you shouldn't be forced to implement it.

Contrast this with say, Ord and Eq. There, the Ord operations are dependent on the Eq ones, so it makes sense to require the subclass to avoid duplication and ensure consistency.

  • But what about the whole Monad, Applicative, Functor deal? They don't depend on each other do they? – semicolon Mar 30 '16 at 4:38
  • In those cases, it's part of the definition. All monads are also applicatives and functors by definition, so you can't fulfill the monad "contract" without fulfilling the others. I'm not familiar enough with the math to know if that's a fundamental relationship or an imposed definition, but either way, we're stuck with it now. – Karl Bielefeldt Mar 30 '16 at 4:58
  • Right... and you can't fulfill the Bounded contract without fulfilling Enum as far as I can tell. It also seems like you can't fulfill the Bounded contract without fulfilling the Ord contract, as how can an unordered type have a max and a min? – semicolon Mar 30 '16 at 5:55
  • 5
    @semicolon The documentation for Bounded says "Ord is not a superclass of Bounded since types that are not totally ordered may also have upper and lower bounds." – Benjamin Hodgson Mar 30 '16 at 11:36
  • @BenjaminHodgson Didn't even think about partially ordered types. +1 for a non-pathological example and for quoting the documentation. – Doval Mar 30 '16 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.