On Mon, Aug 20, 2007 at 03:43:43PM -0300, Isaac Dupree wrote:
Adrian Hey wrote:
I should mention that there's no particular technical reason why an AVL based Data.Map implementation could not provide O(1) size and O(log n) indexing. I just didn't think it was worth the extra cost and effort on my part. It would still cost O(n) in extra heap storage and indexing a Map is bit suspect IMO. The only reasonable use of indexing is covered by the clones OMap type or the AVL zipper I think, and I couldn't think of any good reason why anybody would want the size of a Map unless they were about to do something that was O(n) anyway (or worse).
Maybe a use being "if it's small, do something O(n^2)" or generally, choosing algorithm efficiency based on size (maybe random sampling if it's _really_ big...). I don't suppose there's an easy way to offer caching of information like that to those who have a use for it AT THE SAME TIME AS efficiency, for those who don't...
Sounds like an unsafeTreeHeight would be better...
I don't see a use for _indexing_ either. Reminds be a bit of C++ Boost's multi_container (I think) that could be a map and a sequence and another kind of map all at the same time, sort of...
Paterson's Data.FingerTree already covers just about every uncommon case imaginable with asymptotically very good performace, so there's not much need for indexing operations in Map. (And if people demand a fast structure with both indexing and lookup, we can always specialize again.) The one time I had occasion to use size, I was searching a map using log^2 (n) binary search using a monotonic function of the values; could something like a lazy O(n) assocsSet be added? (then I could use mapMonotonic and not need indexing at all). Stefan