Am Donnerstag 19 November 2009 03:57:56 schrieb Ted Zlatanov: > On Thu, 19 Nov 2009 01:13:23 +0100 Henning Thielemann > <lemm...@henning-thielemann.de> wrote: > > HT> Ted Zlatanov schrieb: > >> On Mon, 16 Nov 2009 00:03:54 +0300 Eugene Kirpichov > >> <ekirpic...@gmail.com> wrote: > > EK> 2009/11/15 Michael Mossey <m...@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] ? _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe