Set, Map libraries

Jan-Willem Maessen jmaessen at
Fri Jun 3 20:33:49 EDT 2005

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

More information about the Glasgow-haskell-users mailing list