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

_______________________________________________

Haskell-Cafe mailing list

[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe