[Haskell-cafe] Re: inversion lists

[Daniel Fischer]

Am Donnerstag 19 November 2009 03:57:56 schrieb 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
>

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]

?