Use UnionListsOrd instead of UnionLists in most places.wip/andreask/unionLists

This should get rid of most, if not all "Overlong lists" errors and fix #20016

1 files changed, 15 insertions, 2 deletions

diff --git a/compiler/GHC/Data/List/SetOps.hs b/compiler/GHC/Data/List/SetOps.hs
index 187d862b3d..dff41991da 100644
--- a/compiler/GHC/Data/List/SetOps.hs
+++ b/compiler/GHC/Data/List/SetOps.hs
@@ -12,7 +12,7 @@
 --
 -- Avoid using them as much as possible
 module GHC.Data.List.SetOps (
-        unionLists, minusList,
+        unionLists, unionListsOrd, minusList,
 
         -- Association lists
         Assoc, assoc, assocMaybe, assocUsing, assocDefault, assocDefaultUsing,
@@ -54,6 +54,19 @@ getNth xs n = assertPpr (xs `lengthExceeds` n) (ppr n $$ ppr xs) $
 -}
 
 
+
+-- | Combines the two lists while keeping their order, placing the first argument
+-- first in the result.
+--
+-- Uses a set internally to record duplicates. This makes it slightly slower for
+-- very small lists but avoids quadratic behaviour for large lists.
+unionListsOrd :: (HasDebugCallStack, Outputable a, Ord a) => [a] -> [a] -> [a]
+unionListsOrd xs ys
+  -- Since both arguments don't have internal duplicates we can just take all of xs
+  -- and every element of ys that's not already in xs.
+  = let set_ys = S.fromList ys
+    in (filter (\e -> not $ S.member e set_ys) xs) ++ ys
+
 -- | Assumes that the arguments contain no duplicates
 unionLists :: (HasDebugCallStack, Outputable a, Eq a) => [a] -> [a] -> [a]
 -- We special case some reasonable common patterns.
@@ -161,7 +174,7 @@ equivClasses cmp items   = NE.groupBy eq (L.sortBy cmp items)
     eq a b = case cmp a b of { EQ -> True; _ -> False }
 
 -- | Remove the duplicates from a list using the provided
--- comparison function.
+-- comparison function. Might change the order of elements.
 --
 -- Returns the list without duplicates, and accumulates
 -- all the duplicates in the second component of its result.