diff options
author | Andreas Klebinger <klebinger.andreas@gmx.at> | 2022-05-09 16:09:39 +0200 |
---|---|---|
committer | Marge Bot <ben+marge-bot@smart-cactus.org> | 2022-05-24 22:13:19 -0400 |
commit | 7c51177d3e135cbba4bc170126c74825fd7bdd61 (patch) | |
tree | 8d11c8bd0e91a1fe0c6f377157a1e6ba2662d410 /compiler/GHC/Data | |
parent | f485d26738c83ef564794b41188e0e082ee59b26 (diff) | |
download | haskell-7c51177d3e135cbba4bc170126c74825fd7bdd61.tar.gz |
Use UnionListsOrd instead of UnionLists in most places.
This should get rid of most, if not all "Overlong lists" errors and fix #20016
Diffstat (limited to 'compiler/GHC/Data')
-rw-r--r-- | compiler/GHC/Data/List/SetOps.hs | 17 |
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. |