[Haskell-cafe] inversion lists

[Henning Thielemann]

Ted Zlatanov schrieb:
> On Mon, 16 Nov 2009 00:03:54 +0300 Eugene Kirpichov <ekirpichov at gmail.com> wrote: 
> 
> EK> 2009/11/15 Michael Mossey <mpm at alumni.caltech.edu>:
>>> Can someone tell me if this is correct. I'm guessing that if I represent
>>> two sets of integers by Word32 (where ith bit set means i is in the set),
>>> then an algorithm to determine if x is a subset of y would go something
>>> like
>>>
>>>
>>>  (y - x) == (y `exclusiveOr` x)
> 
> EK> It's simpler: "x&~y == 0"
> 
> Depending on the OP data set the simple bit vector may be a good
> strategy, but I wonder if an inversion list would be better?  Do you
> expect long runs of adjacent numbers and gaps?  Inversion lists tend to
> encode those much more efficiently than bit vectors.
> 
> I'm just now learning Haskell so I don't know enough to show an
> implementation but inversion lists are very simple conceptually.  If
> your set is (2,3,4,5,8,9,10) the inversion list would be (2,6,8,11).
> It's easy to generate it from a set of Ord elements.


Is "inversion list" = "Gray code" ?