Set, Map libraries

[Jan-Willem Maessen]

On Jun 3, 2005, at 4:47 PM, Adrian Hey wrote:
> On Thursday 02 Jun 2005 10:18 am, Jean-Philippe Bernardy wrote:
>> The definition of the Set datatype being
>>
>> ... [Something strict in all components]
>> It seems you're out of luck when it comes to very large sets.
>>
>> Also, since the structure is strict, it makes little sense to support
>> 4-million-element sets.
>
> I'd be interested to know why you say that. What would you use instead
> if you needed 4-million-element sets?

Replace "4 million" by, say, 2^32 or 2^64 and I think the point stands. 
  The set must fit in your addressable memory, and can thus be counted 
by a similar-sized Int.

Note also that set implementations which cache the size locally will 
have this property in general, whether the rest of the structure is 
strict or not---we'll at least have to compute how many insertions and 
deletions have occurred, and left the thunks kicking around if we 
haven't actually performed them completely yet.

-Jan-Willem Maessen

>
> The AVL trees in my implementation are strict and perfectly capable
> of supporting such sets. Same should be true of Data.Set too AFAICS.
>
> Regards
> --
> Adrian Hey
> _______________________________________________
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users