Why?
Conversation
I now I've come across this in the discourse on type class constraints, but I can't for the life of me remember what to search for to brush up. You'll have to elaborate to explain why this is such a problem.
1
If you haven't watched 's "Type classes vs the world" talk, you should youtu.be/hIZxTQP1ifo. Like , I'm hopeful that a better modular alternative to Haskell-style coherent type classes will be found. I think I'll watch Ed's talk again.
1
1
Yup, seen that one before. I believe he just goes though why it's hard to build an efficient set implementation, but doesn't elaborate on alternatives. Like using module functors or parametrising the type by the dictionary. Will have to watch again.
1
The set thing is just the motivating example (it's to do with a union operation IIRC). The main point is that it's not possible to do that without coherent type classes! The conclusion is that everything else is inferior :)
1
But it _is_ possible – if you are willing to use module functors, or tag your data structure at the type level with ord instance used.
1
1
If your functors are generative then you can't union two sets of ints from two different libraries unless they both defer choice of set implementation by making it a parameter, leaking internals.
If they are applicative then you need to decide equality of comparison functions.
1
2
If you simply tag your data type with which instance you mean then you lose access to common data types. e.g. Compose and (,) dont hold a tag, so now I have to have hundreds of pairs of compositions depending on the attributes of their contents. This damages code reuse badly.
2
Both of these approaches were addressed in the talk.
1
1
Thanks for the clarification. Will have to re-watch it - it's been a while since I did, and it's a long one! 😅
1
2
Any response to this thread ? Might have got lost in the noise 😂 - in the first case, can't you then do a rebuild of the set if the instances don't match, and the second, can't you do an abstraction of the tag?
Rebuilding drastically changes the asymptotic performance of these operations, and you also have to worry whether or not the orderings obey structural equality. You can't even merge the smaller into the larger, but rather must always merge with a given bias for even worse O(...)!