set representation question

[Daan Leijen]

Hi Hal,

On Tue, 11 Nov 2003 16:45:56 -0800 (PST), Hal Daume III <hdaume at ISI.EDU> 
wrote:

> i'm looking for a representation for a set of natural numbers.  right 
> now, my representation is sorted array, which works well.  *all* i care 
> about
> is being able to quickly calculate the size of the intersection of two
> sets.  these sets are, in general, very sparse, which means that the
> intersections tend to be small.

I have a very speedy implementation of "Int" sets based on
big-endian patricia trees in the DData library at:

<http://www.cs.uu.nl/~daan/ddata.html>

You can just pull out the "IntSet.hs" and start using it.

One warning though, it is a general implementation and you might
get better performance using a hand-tuned data structure that is
adapted to your problem set (but than, you might not, since I
paid lots of attention to the bit efficiency of the library ;-)

All the best,
  Daan.