Fast Map Union and Local Instances Through Instance Types

submited by
Style Pass
2023-09-16 10:30:03

In part 31 of my crusade against GHC’s coherence guarantees, I have actually done it! This time we will end up with a way to generate local type class instances without any asterisks about code breaking with optimizations. On the way, we are going to end up solving the dreaded Fast Map Union Problem, combining two of my favorite Haskell tricks, and discovering a bug in a previous version of GHC.

Let’s pretend that Haskell did have consistent locally overridable type class instances. In that case, the interface for Map would be completely broken.

See the issue? Map is some kind of ordered tree internally, so it depends on the Ord instance being consistent across different operations, but with local instances, we don’t have any guarantees like that.

If you think about this for a bit, you may come up with a solution: You can store the instance in the map. This is how most map implementations in other languages work after all.

Leave a Comment