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