Set.intersection

[Christian Maeder]

Christian Maeder wrote:
> Set.intersection is neither left- nor right-biased but biased towards 
> the smaller set. I think that needs to be changed (and that may require 
> a function splitLookup).

Below is my code proposal. I'm not sure if splitLookup should be 
exported. And I'm not sure if splitMember should remain as it is (more 
efficient?) or should be reimplemented using splitLookup (better reuse).

The new intersection function is left-biased and traverses the smaller 
tree also in every recursive call (but I'm not sure if that's better).
The comment "Intersection is more efficient on (bigset `intersection` 
smallset)" needs to be deleted anyway as it is already wrong for the 
current version.

Christian


-- | /O(n+m)/. The intersection of two sets.
intersection :: Ord a => Set a -> Set a -> Set a
intersection Tip t = Tip
intersection t Tip = Tip
intersection t1@(Bin s1 x1 l1 r1) t2@(Bin s2 x2 l2 r2) =
   if s1 >= s2 then
      let (lt,found,gt) = splitLookup x2 t1
          tl            = intersection lt l2
          tr            = intersection gt r2
      in case found of
      Just x -> join x tl tr
      Nothing -> merge tl tr
   else let (lt,found,gt) = splitMember x1 t2
            tl            = intersection l1 lt
            tr            = intersection r1 gt
        in if found then join x1 tl tr
           else merge tl tr


splitMember :: Ord a => a -> Set a -> (Set a,Bool,Set a)
splitMember x t = let (l,m,r) = splitLookup x t in
     (l,maybe False (const True) m,r)

-- | /O(log n)/. Performs a 'split' but also returns the pivot
-- element that was found in the original set.
splitLookup :: Ord a => a -> Set a -> (Set a,Maybe a,Set a)
splitLookup x Tip = (Tip,Nothing,Tip)
splitLookup x (Bin sy y l r)
   = case compare x y of
       LT -> let (lt,found,gt) = splitLookup x l in (lt,found,join y gt r)
       GT -> let (lt,found,gt) = splitLookup x r in (join y l lt,found,gt)
       EQ -> (l,Just y,r)