AVL size

[Adrian Hey]

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