Why can't we have Random class instances derived for enumerations in Haskell?

Question

I wrote this today:

data Door = A | B | C
 deriving (Eq,Bounded,Enum)

instance Random Door where
 randomR (lo,hi) g = (toEnum i, g')
  where (i,g') = randomR (fromEnum lo, fromEnum hi) g
 random = randomR (minBound,maxBound)

And I figured this is roughly copy-pastable for any enumeration. I tried putting Random into the deriving clause, but that failed.

Then I searched the web and found this:

Please provide instance for (Enum a, Bounded a) for Random #21

A few quotes that seem to answer my question, except I don't quite understand them:

What instance do you have in mind, instance (Bounded a, Enum a) => Random a where ...? There can't be such an instance, since it would overlap with every other instance.

This would prevent any user derived instances. ...

Why can't this be automated, by either the deriving clause or with a default implementation at least.

Why wouldn't this work?

instance (Bounded a, Enum a) => Random a where
   randomR (lo,hi) g = (toEnum i, g')
       where (i,g') = randomR (fromEnum lo, fromEnum hi) g
   random = randomR (minBound,maxBound)

Answer 1

The comments are referring to the fact that in Haskell (actually in Haskell with the FlexibleInstances extension), instance matching is done by matching the type without considering the constraints. After the type match succeeds, the constraints are then checked and will generate errors if they aren't satisfied. So, if you define:

instance (Bounded a, Enum a) => Random a where ...

you are actually defining an instance for every type a, not just types a that have Bounded and Enum instances. It's as if you had written:

instance Random a where ...

This will then potentially conflict with any other library-defined or user-defined instances, such as:

newtype Gaussian = Gaussian Double
instance Random Gaussian where ...

There are ways to get around this, but the whole thing ends up getting pretty messy. Also, it can lead to some mysterious compile-type error messages, as noted below.

Specifically, if you put the following in a module:

module RandomEnum where

import System.Random

instance (Bounded a, Enum a) => Random a where
   randomR (lo,hi) g = (toEnum i, g')
       where (i,g') = randomR (fromEnum lo, fromEnum hi) g
   random = randomR (minBound,maxBound)

you'll find that you need the FlexibleInstances extension to allow constraints on instances. That's fine, but if you add that, you'll then see that you need the UndecidableInstances extension. That's maybe less fine, but if you add that, you'll find that you then get an error on the randomR call on the RHS of your randomR definition. GHC has determined that the instance you have defined now overlaps with the built-in instance for Int. (It's actually a coincidence that Int is both Bounded and Enum -- it would have also overlapped with the built-in instance for Double, which is neither.)

Anyway, you can get around this by making your instance overlappable, so that the following:

{-# LANGUAGE FlexibleInstances, UndecidableInstances #-}

module RandomEnum where

import System.Random

instance {-# OVERLAPPABLE #-} (Bounded a, Enum a) => Random a where
   randomR (lo,hi) g = (toEnum i, g')
       where (i,g') = randomR (fromEnum lo, fromEnum hi) g
   random = randomR (minBound,maxBound)

will actually compile.

This is mostly fine, but you may end up with some bizarre error messages. Normally, the following program:

main = putStrLn =<< randomIO

would generate the sensible error message:

No instance for (Random String) arising from a use of `randomIO'

But with the above instance in place, it becomes:

No instance for (Bounded [Char]) arising from a use of ‘randomIO’

because your instance matches String but GHC fails to find a Bounded String constraint.

Anyway, in general, the Haskell community has avoided putting these sorts of catch-all instances into the standard library. The fact that they need the UndeciableInstances extension and OVERLAPPABLE pragmas and potentially introduce a bunch of undesirable instances into a program all leave a bad taste in people's mouths.

So, while it might be technically possible to add such an instance to System.Random, it will never happen.

Likewise, it would be possible to allow Random to be automatically derived for any types that are Enum and Bounded, but the community is reluctant to add additional automatic deriving mechanisms, particularly for type classes like Random that just aren't that often used (compared to say Show or Eq). So, again, it will never happen.

Instead, the standard way of allowing convenient default instances is to define some helper functions that can be used in an explicit instance definition, and that's what's being suggested in the bottom of the proposal you linked. For example, the following functions could be defined in System.Random:

defaultEnumRandomR :: (Enum a, RandomGen g) => (a, a) -> g -> (a, g)
defaultEnumRandomR (lo,hi) g = (toEnum i, g')
       where (i,g') = randomR (fromEnum lo, fromEnum hi) g

defaultBoundedRandom :: (Random a, Bounded a, RandomGen g) => g -> (a, g)
defaultBoundedRandom = randomR (minBound, maxBound)

and people would write:

instance Random Door where
    randomR = defaultEnumRandomR
    random = defaultBoundedRandom

This is the only solution that has a chance of making it into System.Random.

If it does and you dislike having to define explicit instances, you'll be free to stick:

instance {-# OVERLAPPABLE #-} (Bounded a, Enum a) => Random a where
    randomR = defaultEnumRandomR
    random = defaultBoundedRandom

in your own code.