If you compare it with how you'd implement such a data structure using ML modules, it becomes very clear that the bug here is the definition of Data.Heap.Union, not the non-canonicity of type classes.
With ML modules you'd define a Heap module that is parameterised by an Ord module. Different instantiations of the Heap module for the same type `a` but different instances of `Ord a` are different: heaps with Ord1 are of a different type than heaps of Ord2.
From this point of view, passing the Ord instance into each individual heap function call (such as union) is clearly not the right setup. The canonicity of type classes is merely a bandaid for that problem.
Generative functors indeed fixes the issue, but it’s kind of interesting because they’re similar in a way to newtypes. In each case, you generate a new type, distinct from the others, which holds a new implementation of the same interfaces.
It comes down to ergonomics where OCaml’s approach tends to make local reasoning easier and Haskell’s approach makes it a little easier to transform structurally isomorphic types into one another by wrapping/unwrapping.
Probably the last word on this problem hasn't been said, because all approaches seem to have some downsides.
Could you give an example where Haskell's approach makes it easier?
Is this not just moving the problem to a different place? (Maybe it's more ergonomic for some uses)
In Haskell the solution is to use different type parameters via newtypes.
In ML, you define a distinct instantiation of the MaxHeap.
So the difference (in Haskell terms) is something like
`HeapInstantiation1` vs `Heap Wrapped1`
Is this practically a big enough difference to call the Haskell approach wrong? Is it not useful to have a single instantiation able to handle all parameters?
I think one practical disadvantage of the Haskell approach is that you need to wrap and unwrap your types if you want a different ordering on an existing type.
But the main reason why I didn't like the Haskell approach isn't ergonomic but conceptual. To me, the type of the heap should depend on the Ord instance, because the invariant satisfied by the values of type `Heap a` depends on the Ord instance of `a`, not just on the type `a` itself. This invariant is not encoded in the type system in Haskell, but in a dependently typed language you could do that. But in order to even write down the invariant, you need access to the Ord instance.
So the type signature of union could be:
union : {a:Type} → {o:Ord a} → Heap o → Heap o → Heap o
In this case the problem of mixing up heaps with different orderings is ruled out by ordinary type checking, rather than via an extra meta-theoretical invariant satisfied by the language. Although ML modules don't let you encode the invariant either, they at least set it up in the same way, because the type Heap(o).t depends on the o and not just on o.t, and the type checker also views it that way and will say Heap(o).t ≠ Heap(o').t even when o.t = o'.t.
In Haskell on the other hand, if we desugar type classes to passing around records, then we can suddenly break the invariant in type safe code.
Maybe I'm imposing values on Haskell that have no practical significance in that context, but to me the way Haskell does it feels like a hack.
With ML modules you'd define a Heap module that is parameterised by an Ord module. Different instantiations of the Heap module for the same type `a` but different instances of `Ord a` are different: heaps with Ord1 are of a different type than heaps of Ord2.
From this point of view, passing the Ord instance into each individual heap function call (such as union) is clearly not the right setup. The canonicity of type classes is merely a bandaid for that problem.