Container element types

Question

In a way this is a step backwards from my earlier question, but... Can somebody remind me why this doesn't work?

class Container c e where
  empty :: c
  insert :: e -> c -> c

instance Container [x] x where
  empty = []
  insert = (:)

instance Container ByteString Word8 where
  empty = BIN.empty
  insert = BIN.cons

instance Ord x => Container (Set x) x where
  empty = SET.empty
  insert = SET.insert

Obviously if it was that easy, nobody would have bothered to invent functional dependencies nor associated types. So what's the problem with the above?

Answer 1

There is nothing to stop you from adding instance Container [Int] Int and instance Container [Int] Char, and when you ask for empty :: [Int] the compiler has no way of knowing which instance it's supposed to come from.

"Ah, but I only have instance Container [Int] Int," you say. "And an instance Container [Int] Char would be a bug anyway."

But the compiler cannot know that you will not add an instance Container [Int] Char in the future, and if you do, it is not allowed for it to break your existing code.

So we need some way of telling the compiler that

• the first parameter of Container uniquely determines the second parameter of Container
• if it sees different instances that differ only in the second type, that indicates a bug

Enter functional dependencies.