[Haskell-cafe] How to design default implementations of type class methods?

Henning Thielemann lemming at henning-thielemann.de
Mon Nov 6 12:34:07 EST 2006


I like to hear some opinions about how to implement class method defaults.

Let's consider the following example:
 I want to classify types which allow for computation of the greatest
common divisor. The greatest common divisor can be computed by Euclid's
algorithm in some cases (integers, univariate polynomials) but not in all
cases (integer matrices, multivariate polynomials). So maybe it's a good
idea to set the Euclidean algorithm as default implementation for the GCD
method. Say, I have already implemented both the normal Euclidean
algorithm as "euclid", which only emits the GCD, and the extended
Euclidean algorithm "extendedEuclid" which also determines a and b in
"gcd(x,y) = a*x + b*y" for given x and y.

Now I have two choices for implementing default methods:

1. Implement a method by calling other methods of the same class.

   class (Units a) => PID a where
       extendedGCD :: a -> a -> (a,a,a)
       extendedGCD = extendedEuclid divMod

       gcd         :: a -> a -> a
       gcd x y     = let (g,_,_) = extendedGCD x y in g

   Advantage: User must implement only few methods,
              here extendedGCD, the other ones work automatically.
   Disadvantage: User must know, how the default methods call each other,
                 in order to not introduce cycles.

2. Implement a method by calling custom code,
   preferably a public function according to
      http://www.haskell.org/haskellwiki/Slim_instance_declaration

   class (Units a) => PID a where
       extendedGCD :: a -> a -> (a,a,a)
       extendedGCD = extendedEuclid divMod

       gcd         :: a -> a -> a
       gcd         = euclid mod

   Advantages/Disadvantages are negated with respect to the first item. :-)


Ok, this example class is not well chosen, because in the case of
multivariate polynomials, not only extended Euclidean algorithm fails, but
it is in many cases not possible to represent the GCD of x and y as a
linear combination of x and y.

My question is not limited to this case: I want to know, what reasons
exist pro and cons each alternative. Currently I prefer the first way,
because it reduces the work of implementing instances to the things that
are essential for the particular type. People who want specialized and
more efficient methods, must implement all methods.


More information about the Haskell-Cafe mailing list