From: Niklas Hambuechen <[email protected]> For n*log(n) duplicate removal (as opposed to nub's n^2).
Signed-off-by: Niklas Hambuechen <[email protected]> Signed-off-by: Petr Pudlak <[email protected]> Reviewed-by: Klaus Aehlig <[email protected]> Cherry-picked-from: 5dd8067d Signed-off-by: Klaus Aehlig <[email protected]> --- src/Ganeti/Utils.hs | 10 ++++++++++ 1 file changed, 10 insertions(+) diff --git a/src/Ganeti/Utils.hs b/src/Ganeti/Utils.hs index e3d865f..6e342d1 100644 --- a/src/Ganeti/Utils.hs +++ b/src/Ganeti/Utils.hs @@ -90,6 +90,7 @@ module Ganeti.Utils , safeRenameFile , FilePermissions(..) , ensurePermissions + , ordNub ) where import Control.Concurrent @@ -751,3 +752,12 @@ safeRenameFile perms from to = do _ <- ensurePermissions dir perms renameFile from to return $ either (Bad . show) Ok (result :: Either IOError ()) + +-- | Removes duplicates, preserving order. +ordNub :: (Ord a) => [a] -> [a] +ordNub = + let go _ [] = [] + go s (x:xs) = if x `S.member` s + then go s xs + else x : go (S.insert x s) xs + in go S.empty -- 2.5.0.rc2.392.g76e840b
