Re: [Haskell-cafe] Re: inversion lists

Am Donnerstag 19 November 2009 03:57:56 schrieb Ted Zlatanov:

On Thu, 19 Nov 2009 01:13:23 +0100 Henning Thielemann wrote:

HT> Ted Zlatanov schrieb:

...

...

On Mon, 16 Nov 2009 00:03:54 +0300 Eugene Kirpichov wrote:

EK> 2009/11/15 Michael Mossey :

...

...

...

...

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

like: h :: Num a => a -> [a] -> [a] h x (y:ys) | x+1 == y = x:ys h x zs = x:(x+1):zs invlist = foldr h [] ghci> invlist [2,3,4,5,8,9,10] [2,6,8,11] ghci> invlist [4] [4,5] ghci> invlist [1,2,3,4,7,8,9,13,14,15,20,22] [1,5,7,10,13,16,20,21,22,23] ?