On Wednesday 01 Mar 2006 4:01 pm, Christian Maeder wrote:
Adrian Hey wrote:
What were your keys, btw?
data ShATerm = ShAAppl String [Int] [Int]
| ShAList [Int] [Int] | ShAInt Integer [Int]
deriving (Eq, Ord)
(where the last list is always empty)
and something (with short strings) like:
data Id = Id [String] [Id]
I think this sort of thing is good illustration of why I don't think the indirection overhead of implementing Maps as AVL trees of association pairs will matter much in practice. Chances are that it will only be used in circumstances where indirection cost is trivial compared to comparison costs. There's also a small saving in heap burn rate too (1 less field per tree node). It also illustrates why I'm now quite sceptical about the use of any balanced tree implementation of sets and maps. It should only really be used as a default first implementation of JPB's API which will work for any instance of Ord, but it will never be very efficient for non-trivial Key types IMO. I think what we should be aiming for in the long term is automatically derived Generalised Tries (as discussed recently). Regards -- Adrian Hey