-splitMember x Tip = (Tip,False,Tip)
-splitMember x (Bin sy y l r)
- = case compare x y of
- LT -> let (lt,found,gt) = splitMember x l in (lt,found,join y gt r)
- GT -> let (lt,found,gt) = splitMember x r in (join y l lt,found,gt)
- EQ -> (l,True,r)
+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)