AVL size

Adrian Hey wrote:

...

Is AVL compatible enough that I would only need to change the imports to test this?

Also, size is O(n), not O(1). (But the only reason this is O(1) with Data.Map is that you pay extra for this information on every operation that created the Map in the first place).

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? 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)) Isaac