Set, Map libraries

Adrian Hey ahey at iee.org
Sat Jun 4 01:28:47 EDT 2005


On Saturday 04 Jun 2005 1:33 am, Jan-Willem Maessen wrote:
> 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.

I'm afraid I still don't really understand point we're debating, so
can't comment on whether or not it stands (unless the point is
that you can't deal with sets that won't fit in available memory :-)

Is that all we're discussing here? Or maybe it's a point about word
size used to represent Ints? JPB's remarks about strictness led me
to suspect there might be some unstated algorithmic insight behind
them (like a lazy implementation would not be so limited, or would
offer better performance or space behaviour perhaps). But maybe I
was wrong.

Regards
--
Adrian Hey



More information about the Glasgow-haskell-users mailing list