Set, Map libraries
jmaessen at alum.mit.edu
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.
> The AVL trees in my implementation are strict and perfectly capable
> of supporting such sets. Same should be true of Data.Set too AFAICS.
> Adrian Hey
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
More information about the Glasgow-haskell-users