David Roundy wrote:
On Mon, Sep 17, 2007 at 11:07:10AM +0100, Adrian Hey wrote:
Ketil Malde wrote:
What would the disadvantages be to replacing Data.Map with this implementation? Personally I don't really like the idea of Data.Map, Data.Map.AVL or any other lib becoming entrenched as official or de-facto standards. It seems like a recipe for stagnation to me. IMHO such libs just shouldn't be bundled with ghc (or any other compiler) for this reason.
To me, it seems like a recipe for usefulness. It would allow data structures to be used in multiple libraries. Competing packages is fine and dandy for something like an XML parser or DBM interface, but I'd like data structures to be standard
I don't see fundamental difference between these. Why is so important that libs all use the same Maps but not important that they all use the same XML parser or DBM interface? If your gonna standardise you'd better be pretty sure about what it is that gets written in stone. I suspect that most Data.Map users are unaware that on performance grounds it would be hard to make a worse choice than the data structure currently used by Data.Map. It's the worst of all balanced tree implementations I've benchmarked. Furthermore any balanced tree implementation (including Data.Map and the AVL clone) will likely suck performance wise for non-trivial key types (even strings). But some will suck less than others.
so that other packages can use them in their interfaces without putting undue burden on their users (and without the users being forced to figure out how to convert back and forth between various different Data.Map.*).
I would consider it exceedingly poor design to produce a lib that mentioned (Data.)Map in it's API, precisely because that pretty much rules out the possibility of using any more efficient future map implementations without an API change. Ideally the way to deal with this is via standardised interfaces (using type classes with Haskell), not standardised implementations. Even this level of standardisation is not a trivial clear cut design exercise. e.g we currently have at least two competing class libs, Edison and the collections package. Which one should become standard? Regards -- Adrian Hey