10

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

6
  • 3
    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, 2016 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, 2016 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, 2016 at 2:46
  • 2
    @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, 2016 at 4:35
  • 1
    @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, 2016 at 8:26

2 Answers 2

9

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 >:.

5
  • 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, 2016 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. Mar 30, 2016 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, 2016 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 Apr 13, 2016 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, 2016 at 23:29
4

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.

9
  • 1
    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. Mar 30, 2016 at 4:58
  • 6
    @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." Mar 30, 2016 at 11:36
  • 1
    @BenjaminHodgson Didn't even think about partially ordered types. +1 for a non-pathological example and for quoting the documentation.
    – Doval
    Mar 30, 2016 at 14:21
  • 2
    @semicolon An example of a partial ordering from the world of computers might be subtyping in OO languages. Writing <: for is a subtype of, ∀ T S. T <: S ∨ S <: T does not hold (eg, int !<: bool ∧ bool !<: int). You'd likely run into this if you were writing a compiler. Mar 30, 2016 at 16:01
  • 1
    @BenjaminHodgson ah ok. So for example if A is a superclass of B and C, and D is a subclass of B and C, then B and C are incomparable but A and D are max/min?
    – semicolon
    Mar 30, 2016 at 16:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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