[Haskell-cafe] reply to vincent foley's question about poker

[Luke Palmer]

On Sun, Mar 9, 2008 at 3:21 AM, Thomas Hartman <tphyahoo at gmail.com> wrote:
>  instance (Enum a, Bounded a) => Arbitrary a where
>   arbitrary = do n <- choose (fromEnum (minBound :: a), fromEnum
>  (maxBound :: a) )
>                  return $ toEnum n

I really think it's a bad idea to allow undecidable instances.  While
it may seem to work for small problems, when you start using
undecidable instances in larger pieces of software, you will get
elusive typecheker errors (stack overflows / infinite loops) which
magically appear and disappear with small changes to the code.

You probably already know this, but the evil of undecidable instances
makes itself pretty apparent once you understand how the typeclass
algorithm works.  Here's how it goes, anthropomorphically:

* I see a call to arbitrary; I will call its return value "a".  The
call to arbitrary comes with the constraint "Arbitrary a".
... in the future, when generalizing the type ...
* I see that "a" has be unified to "[b]" (for some b).  I need an
instance for "Arbitrary [b]".  Ah, here's one (seeing the instance
above).  Now I have "Arbitrary [b]", and I thus have to add the
constraints "Enum [b]" and "Bounded [b]"
... continue solving...

The thing to note is that we did not *check* that we had "Enum [b]"
and "Bounded [b]" before using the instance "Arbitrary [b]"; rather it
worked the other way round:  We found an instance "Arbitrary [b]" and
that induced some new constraints for us.  That means that if you
have, say, these two instances:

   instance (Arbitrary a) => Aribtrary [a]
   instance (Enum a, Bounded a) => Aribtrary a

If you have a list type that you need to be an instance of Aribtrary,
if you're unlucky it will pick the second one and you'll end up with
Enum [a] and Bounded [a], which won't be satisfiable.  There is no
backtracking, you just get a type error where there (according to you)
should not be one.  I believe GHC has some rules to minimize the
occurences of such "unluckiness", but they're just heuristic and don't
provide any guarantee (and thus only propagate the illusion that
instances like this are actually okay).

This is an example where undecidable instances will lead to
indeterminate behavior, but there are other trickier cases where you
get an infinite loop, which is fixable only by knowing how the
algorithm works and placing a type annotation in the most obscure
corner of some function.

Okay, now that that rant is done, what is the safe way to accomplish
what you want?  Wrap it in a newtype:

    newtype EnumArbitrary a = EnumArbitrary { fromEnumArbitrary :: a }
    instance (Enum a, Bounded a) => Arbitrary (EnumArbitrary a) where ...

This is a perfectly fine, well behaved H98 instance.  You mark when
you want to use this instance by appearances of the constructor
EnumArbitrary, so you don't run into cases like the above.

However, many times for usability purposes I run into situations where
I want a generic instance like the one you used.  Props to anyone who
can come up with a typeclass system which allows such things and has
decidable and predictable inference.

Luke