Isaac Dupree wrote:
Since it's a fairly well balanced tree, I would think there could be an "approximate size" in O(log(n)) time? Of course this would be another exported function... would making it produce equal results for all equal maps be difficult?
I did consider something like this. It's certainly true that you could derive definite upper and lower bounds on size in O(log n) time. Trouble is, the result of this would depend of details of tree structure which AVL and Data.Map make non-observable by defining equality in terms of (association) lists. So if a function like this was exposed you could have two "equal" trees (Maps) that gave different answers. 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).
Also there is are "small length"-like functions that tell what the size of something is, up to a point, or "more than that"; this can probably be done with lazy "elems"? (e.g. minMapSize of two maps, at O(min(m,n))
Yes, something like this would be possible and easy. I'll think about adding it. Regards -- Adrian Hey