Using subclass implementation in the definition of superclass functions

Question

In my Haskell program I have some typeclasses representing abstract notions of "shapes", namely

-- | Class representing shapes.
class Shape a where
  isColliding :: (Shape b) => a -> b -> Bool
  centroid :: Point

-- | Class representing shapes composed of a finite number of vertices 
and line segments connecting them.
class (Shape a) => Polygon a where
  vertices :: a -> Vertices 

As you can see, Polygon is naturally a subclass of Shape. I also have some data types that are instances of these different typeclasses. For example:

data Box = Box Point Point Angle

instance Shape Box where
  ...

instance Polygon Box where
  ...

---------------------------------

data Circle = Circle Point Radius

instance Shape Circle where
  ...

I have many more possible shapes, such as NGon, RegularNGon, etc. I would like to be able to implement isColliding, but the information required to calculate whether two shapes are colliding is dependent upon the implementation of the specific instance of Shape. For example, to calculate if two boxes are colliding, I need their list of vertices. So I have a few questions:

1. Is there anyway to "specialize" my function isColliding so that it is defined in a specific way for collisions of the type isColliding :: (Polygon b) => Box -> b -> Bool?
2. Is the structuring of my datatypes the best way to approach this problem, or am I misusing typeclasses and datatypes when the whole thing could be restructured to eliminate this problem?

I am rather new to Haskell, so if my question is worded poorly or any clarification is needed, please tell me.

Answer 1

Your current Shape class says “isColliding can tell whether this shape intersects another shape using only the methods of Shape on the other shape”, because its signature (Shape b) => a -> b -> Bool only tells you that b has an instance of Shape. So you’re right that this isn’t quite what you want.

One thing you can do is use MultiParamTypeClasses to describe a relationship between two types:

{-# LANGUAGE MultiParamTypeClasses #-}

class Colliding a b where
  collidesWith :: a -> b -> Bool

And then make instances for various concrete combinations of types:

instance Colliding Circle Box where
  Circle p r `collidesWith` Box p1 p2 θ = {- … -}

Here you know the concrete types of both a and b when defining the implementation. That might be good enough for your use case.

However, this leaves you with n² instances if you have n types. And you’ll run into problems if you try to define polymorphic instances like this:

instance (HasBoundingBox b) => Colliding Circle b where
  collidesWith = {- … -}

Because this overlaps with all your other instances for Colliding Circle: b will match any type, and only add the constraint that b must have an instance of HasBoundingBox. That constraint is checked after instance resolution. You can work around this with OverlappingInstances or the newer OVERLAPPABLE/OVERLAPPING/OVERLAPS pragmas to tell GHC to choose the most specific matching instance, but this might be more trouble than it’s worth if you’re just getting familiar with Haskell.

I’d have to think on it more, but there are definitely alternative approaches. In the simplest case, if you only need to deal with a few different kinds of shape, then you can just make them a single sum type instead of separate data types:

data Shape
  = Circle Point Radius
  | Box Point Point Angle
  | …

Then your isColliding function can be of type Shape -> Shape -> Bool and just pattern-match on this type.

Generally speaking, if you’re writing a typeclass, it should come with laws for how instances should behave, like mappend x mempty == mappend mempty x == x from Data.Monoid. If you can’t think of any equations that should always hold for instances of your class, you should prefer to represent things with plain old functions and data types instead.