Using Haskell type classes to enforce commutativity

Question

I want to define a type class for geometric objects that can be intersected together:

class Intersect a b c | a b -> c where
  intersect :: a -> b -> c
-- Language extensions: -XMultiParamTypeClasses, -XFunctionalDependencies

The idea is to have a general-purpose intersection functions that can handle objects of different types. One could imagine such instances as

instance Intersect Line Plane (Maybe Point) where
  ...
instance Intersect Plane Plane (Maybe Line) where
  ...

But I also want to declare that intersection is commutative:

instance (Intersect a b c) => Intersect b a c where
  intersect x y = intersect y x
-- Language extensions: -XUndecidableInstances

The problem is that whenever I evaluate intersect x y without first defining an instance of the form Intersect a b c, where a is the type of x and b is the type of y, the program goes into an infinite loop, presumably caused by recursive instance declaration about commutativity. Ideally I want something like intersect Egg Bacon to fail to type-check because no such instance was defined, not trap me in an infinite loop. How can I implement this?

Answer 1

First, you could use the commutative package, in which case you would modify the type signature of intersect to the following, but otherwise the rest of your code would "just work":

instersect :: Commutative a b -> c

However, you can also use QuickCheck with hspec in order to run a property test on all instances of your typeclass to ensure that it does in fact commute. This may reduce overhead - you'd have to do a benchmark since I don't know off the top of my head. For instance:

import Test.Hspec

main :: IO ()
main = hspec $ do
    describe "intersect" $ do
        parallel $ it "should commute" $ do
            property $ \x y -> intersect x y == intersect (y :: Point) (x :: Line)