[Haskell-cafe] Re: inversion lists

[Ted Zlatanov]

On Thu, 19 Nov 2009 01:13:23 +0100 Henning Thielemann <lemming at henning-thielemann.de> wrote: 

HT> 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.

HT> Is "inversion list" = "Gray code" ?

No.  An inversion list contains the boundaries of all the continuous
intervals in the input.  In other words, any time you see input of
[n,n+1, n+2...n+k,n+m...] where m > k+1 your inversion list gets the
entries n and n+k+1.

As I said I'm just starting to learn Haskell so I can't give a proper
implementation:

isSuccessor:: (Num a) => a -> a -> Bool
isSuccessor x y = x+1 == y

inversion :: (Num a) => [a] -> [a]
inversion [] = []
inversion (x:xs) = x:(inversion . dropWhile isSuccessor xs)

The above is obviously broken, but the idea is to drop successive
elements.  I don't know how to do that in a predicate for dropWhile so I
may need a different function from Data.List or elsewhere.

Ted