diff options
Diffstat (limited to 'compiler/utils')
| -rw-r--r-- | compiler/utils/ListSetOps.hs | 9 |
1 files changed, 8 insertions, 1 deletions
diff --git a/compiler/utils/ListSetOps.hs b/compiler/utils/ListSetOps.hs index 1a134d5dc8..8a6e07d84a 100644 --- a/compiler/utils/ListSetOps.hs +++ b/compiler/utils/ListSetOps.hs @@ -14,7 +14,7 @@ module ListSetOps ( Assoc, assoc, assocMaybe, assocUsing, assocDefault, assocDefaultUsing, -- Duplicate handling - hasNoDups, removeDups, findDupsEq, + hasNoDups, removeDups, findDupsEq, insertNoDup, equivClasses, -- Indexing @@ -169,3 +169,10 @@ findDupsEq _ [] = [] findDupsEq eq (x:xs) | null eq_xs = findDupsEq eq xs | otherwise = (x :| eq_xs) : findDupsEq eq neq_xs where (eq_xs, neq_xs) = partition (eq x) xs + +-- | \( O(n) \). @'insertNoDup' x xs@ treats @xs@ as a set, inserting @x@ only +-- when an equal element couldn't be found in @xs@. +insertNoDup :: (Eq a) => a -> [a] -> [a] +insertNoDup x set + | elem x set = set + | otherwise = x:set |