thsutton / rawr Goto Github PK

Properties testing intersection :: Chunk -> Chunk -> Chunk failed on very small test cases (e.g. intersection [0] [0]).

The underlying cause was a bug which was possible too little polymorphism in the definition of vMergeWith which allowed a bug when the process was short-circuited due to an empty vector on either side:

vMergeWith :: (G.Vector vector e, Ord e)
           => (Maybe e -> Maybe e -> Maybe e)
           -> vector e -> vector e -> vector e
vMergeWith f as bs
  | G.null as = bs
  | G.null bs = as
  | otherwise = ...

The intersection function should not include any chunks without a corresponding chunk in the other input but the bad implementation of vMergeWith was automatically accepting them.

Making vMergeWith more polymorphic in the elements in the result vector turns this bug into a type error:

vMergeWith :: (G.Vector vector e, G.Vector vector r, Ord e)
           => (Maybe e -> Maybe e -> Maybe r)
           -> vector e -> vector e -> vector r
vMergeWith f as bs
  | G.null as = G.concatMap (\e -> maybe G.empty G.singleton $ f Nothing (Just e)) bs
  | G.null bs = G.concatMap (\e -> maybe G.empty G.singleton $ f (Just e) Nothing) as
  | otherwise = ...

Implement all operations of Bits typeclass.

We have an "official" Roaring format specification that this library should be able to at least partially support...

https://github.com/RoaringBitmap/RoaringFormatSpec