diff options
Diffstat (limited to 'src/compiler/GF/Data')
| -rw-r--r-- | src/compiler/GF/Data/Utilities.hs | 19 |
1 files changed, 17 insertions, 2 deletions
diff --git a/src/compiler/GF/Data/Utilities.hs b/src/compiler/GF/Data/Utilities.hs index eac315508..29ed329dc 100644 --- a/src/compiler/GF/Data/Utilities.hs +++ b/src/compiler/GF/Data/Utilities.hs @@ -12,12 +12,12 @@ ----------------------------------------------------------------------------- -module GF.Data.Utilities(module GF.Data.Utilities, module PGF.Utilities) where +module GF.Data.Utilities(module GF.Data.Utilities) where import Data.Maybe import Data.List import Control.Monad (MonadPlus(..),liftM,when) -import PGF.Utilities +import qualified Data.Set as Set -- * functions on lists @@ -190,3 +190,18 @@ joinS glue = concatS . intersperse (showString glue) +-- | Like 'Data.List.nub', but O(n log n) instead of O(n^2), since it uses a set to lookup previous things. +-- The result list is stable (the elements are returned in the order they occur), and lazy. +-- Requires that the list elements can be compared by Ord. +-- Code ruthlessly taken from <http://hpaste.org/54411> +nub' :: Ord a => [a] -> [a] +nub' = loop Set.empty + where loop _ [] = [] + loop seen (x : xs) + | Set.member x seen = loop seen xs + | otherwise = x : loop (Set.insert x seen) xs + + +-- | Replace all occurences of an element by another element. +replace :: Eq a => a -> a -> [a] -> [a] +replace x y = map (\z -> if z == x then y else z) |