Avoid two-layers of pattern matchin in `union` (#537)
authorJoachim Breitner <mail@joachim-breitner.de>
Tue, 20 Feb 2018 15:34:45 +0000 (10:34 -0500)
committerDavid Feuer <David.Feuer@gmail.com>
Tue, 20 Feb 2018 15:34:45 +0000 (10:34 -0500)
by matching on the size field instead. I expect this to yield (slightly)
more efficient code. According to the benchmark, this yields a 4% speed
improvement for `union` and 3% for `unions`.

Data/Set/Internal.hs

index 816d9c0..5800d98 100644 (file)
@@ -715,8 +715,8 @@ unions = foldlStrict union empty
 -- equal elements are encountered.
 union :: Ord a => Set a -> Set a -> Set a
 union t1 Tip  = t1
 -- equal elements are encountered.
 union :: Ord a => Set a -> Set a -> Set a
 union t1 Tip  = t1
-union t1 (Bin _ x Tip Tip) = insertR x t1
-union (Bin _ x Tip Tip) t2 = insert x t2
+union t1 (Bin 1 x _ _) = insertR x t1
+union (Bin 1 x _ _) t2 = insert x t2
 union Tip t2  = t2
 union t1@(Bin _ x l1 r1) t2 = case splitS x t2 of
   (l2 :*: r2)
 union Tip t2  = t2
 union t1@(Bin _ x l1 r1) t2 = case splitS x t2 of
   (l2 :*: r2)