AVL size

[Stefan O'Rear]

On Mon, Aug 20, 2007 at 03:43:43PM -0300, Isaac Dupree wrote:
> Adrian Hey wrote:
>> 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).
>
> Maybe a use being "if it's small, do something O(n^2)" or generally, 
> choosing algorithm efficiency based on size (maybe random sampling if it's 
> _really_ big...).  I don't suppose there's an easy way to offer caching of 
> information like that to those who have a use for it AT THE SAME TIME AS 
> efficiency, for those who don't...

Sounds like an unsafeTreeHeight would be better...

> I don't see a use for _indexing_ either. Reminds be a bit of C++ Boost's 
> multi_container (I think) that could be a map and a sequence and another 
> kind of map all at the same time, sort of...

Paterson's Data.FingerTree already covers just about every uncommon case
imaginable with asymptotically very good performace, so there's not much
need for indexing operations in Map.  (And if people demand a fast
structure with both indexing and lookup, we can always specialize
again.)

The one time I had occasion to use size, I was searching a map using
log^2 (n) binary search using a monotonic function of the values; could
something like a lazy O(n) assocsSet be added?  (then I could use
mapMonotonic and not need indexing at all).

Stefan
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org/pipermail/libraries/attachments/20070820/7443bc5c/attachment.bin