[Haskell-cafe] Re: inversion lists
Ted Zlatanov
tzz at lifelogs.com
Wed Nov 18 21:57:56 EST 2009
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
More information about the Haskell-Cafe
mailing list