[Haskell-cafe] Minimal complete definitions

George Pollard porges at porg.es
Mon Dec 15 21:45:49 EST 2008

Good afternoon Café,

I've written a little bit of code to calculate minimal complete
definitions for a class given which of its functions use which other

As an example:

doDependencies ord =

doDependencies num =

The first part of the pair is those functions which must *always* be
implemented, the second part is a list of possible minimal complete
definitions available for the provided list.

This can help catch mistakes; a comment in the GHC source for
GHC.Classes notes that compare must be implemented using (<=) and not
(<) in order to give the minimal complete definition (<= OR compare). If
we use the incorrect (<) then my code calculates the MCD as:

doDependencies wrongOrd =

That is, the MCD is (< OR (< AND <= AND compare) OR compare).

Now I have two questions:

1) Is my code correct? ;)
2) Could this be incorporated into GHC in order to detect when someone
hasn't provided a sufficient definition for a class? As an example, it
could detect this:

> ~$ cat test2.hs
> data Die d = Die d
> instance Eq (Die d) where
> main = do
> let i = Die "stack overflow"
> print (i == i)
> ~$ ghc -Wall test2.hs --make
> ~$ ./test2
> Stack space overflow: current size 8388608 bytes.
> Use `+RTS -Ksize' to increase it.

Given the following:

doDependencies [("==", Just ["/="]),("/=", Just ["=="])] =

GHC could warn that either (==) or (/=) must be implemented.

- George
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 197 bytes
Desc: This is a digitally signed message part
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20081216/4eaad080/attachment.bin

More information about the Haskell-Cafe mailing list