@MartinS, that doesn’t sound plausible to me. It needs a certain data structure, so you end up writing code a certain way and small details are important.
@Janiczek, not sure! I believe the approach I use is called HM(X). It lets you have variants like HM(=) for languages like Elm and HM(≤) for languages like Scala with subtyping.
@Philipp_Krueger, it is true about using a greedy algorithm, but that refers to the order of solving constraints. GHC can reach a type class constraint that it cannot solve right now. Maybe you have
(Num a) => a but I do not know what
a is yet. So it kicks this constraint to the end of the queue. Solving more equality constraints may reveal that
a is an
Int, so when they get to that type class constraint again later on, there is enough information to solve it. It’s probably true that this has a perf cost, but I suspect it’s pretty small. Especially compared to using union-find or not! (E.g. Scala cannot use union-find in all cases because it doesn’t work well with subtyping. That’s a big deal for perf there AFAIK!)
I dug around the file you mention, but it all seems to be happening in
TcM which is a type alias for an
IOEnv which gives you access to
IORef values which are needed for union find.