AVL size

Isaac Dupree isaacdupree at charter.net
Mon Aug 20 07:28:03 EDT 2007

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


More information about the Libraries mailing list