Type classes, associated families -> containers, keys, and elements: Who is who?

Question

Reading about type families on haskellwiki, I see the example

class Collects ce where
  type Elem ce
  empty  :: ce
  insert :: Elem ce -> ce -> ce

This makes sense to me, as I use my (possibly counterproductive) OOP metaphors - an instance of Collects HAS A associated type (synonym) Elem ce. The collection is somehow 'bigger' than the elements.

I'm confused by the example for associated data families because it doesn't fit that model.

 class GMapKey k where
   data GMap k :: * -> *
   empty       :: Gmap k v
   insert      :: k -> v -> GMap k v -> Gmap k v

The map collects vs and feels 'bigger' than the vs and the ks. But it seems like GMapKey HAS an associated GMap, when I expected the relationship to go the other way.

When I'm choosing between data families and type synonym families, is this the pattern to follow (data families: container is the associated type, type synonym families: element is the associated type)? Or is this IS A / HAS A distinction irrelevant, and the two examples could have been interchanged?

Answer 1

I'd suggest thinking of it this way: the GMap family is associated with k, and you must have a GMap type family instance associated with k for k to be used as a GMapKey.

The choice between these options is more dependent on your needs than anything else. The GMap k approach is preferable when the key type dictates the map implementation: e.g. use an IntMap for Int keys, but use another type of Map for other keys...

Answer 2

The IS A/HAS A relation is a bad metaphor here. A better intuition would be "ASSOCIATES WITH" or "SPECIALIZES (some type) TO". In practice it means that when you resolve a type

f :: GMapKey k => k -> GMap k v -> v

both the first and second parameters are polymorphic but must unify together. It's not necessary that one is contained within the other.

---

To decide which "direction" to use you have to think about how things generalize. If you define a class of "containers" which associated types for the "key" then you're saying that each container type "instantiates this class interface" on a single key. This is a many-to-one relationship since each "container" has a single associated "key" but "keys" can be the associated types for many containers. If you go the other way, you're stating that each "key" restricts to a specific kind of "container", but containers might have many different keys which can index them.