Jeff Harper defined typeclasses
class Reciprocate a b | a -> b where recip :: a -> b class Multiply a b c | a b -> c where (*) :: a -> b -> c
and encountered the problem with
-- Here I define a default (/) operator that uses the -- Reciprocate and Multiply class to perform division. class (Reciprocate b recip, Multiply a recip c) => Divide a b c | a b -> c where (/) :: a -> b -> c (/) x y = x * (recip y)
which doesn't work, because the type variable 'recip' doesn't appear in the class head. He wrote
I also, wonder if it would be appropriate to include in future versions of Haskell, the ability to infer functional dependences in a new class definition, so that my first attempt at a definition of class Divide works.
I'm afraid there may be the problem with the example rather than with Haskell. Let us suppose that the above definition of Divide works. Jeff Harper writes elsewhere
However, taking the reciprocal and then multiplying may not always be the best way of dividing. So, I'd like to put this into a divide class, so (/) can be defined differently for different types.
The key phrase is that we wish (/) defined differently for different types, because using reciprocals is not always the best way of dividing. Then why do we insist that every instance of Divide must be also an instance of Reciprocate (because that's what the definition of Divide says)? Why is that that whenever we divide something by the value of type 'b', it must be possible to reciprocate that value of type b? Even if we don't use reciprocals in the division? If we assume that we need Reciprocate only if we are going to use the 'default' method, the solution becomes obvious. It does involve overlapping and undecidable instances, sorry. These extensions are really useful in practice. Here's the solution:
class Divide a b c | a b -> c where (/) :: a -> b -> c
Here's the most general instance. It applies when nothing more specific does. It is in this case that we insist on being able to take the reciprocal:
instance (Reciprocate b recip, Multiply a recip c) => Divide a b c where (/) x y = x * (recip y)
Now, a specific instance only for Integers, which involves no reciprocals:
instance Divide Integer Integer (Ratio Integer) where (/) = (%)
Another specific instance. It too involves no reciprocals. Incidentally, the posted code does not even define an instance of Reciprocate for Ints!
instance Divide Int Int (Ratio Integer) where x / y = (fromIntegral x) % (fromIntegral y)
A few tests:
test0 = (1::Int) / (2::Int) test1 = (1::Integer) / (2::Integer) test2 = (1::Double) /(2::Double)
P.S. A remark for Haskell': the most general instance above (repeated below)
instance (Reciprocate b recip, Multiply a recip c) => Divide a b c where (/) x y = x * (recip y)
shows why we can never be satisfied with only decidable instances -- why we need the undecidable instances extension. The instance makes it clear that we cannot decide if the instance selection process for Divide terminates just by looking at this instance. There is no information to decide on termination: we must examine instances of Reciprocate and Multiply (in particular, we should check if those instances refer back to Divide). Thus, no _local_ instance termination criterion would ever be able to handle above instance. OTH, it seems quite unreasonable to require a Haskell system to employ a global instance selection termination criterion (short of recursion stack limit or other such `dynamic' test).