-- | Basic utilities
module PGF.Utilities where
import Data.Set(empty,member,insert)


-- | 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' :: [a] -> [a]
nub' = Set a -> [a] -> [a]
forall a. Ord a => Set a -> [a] -> [a]
loop Set a
forall a. Set a
empty
    where loop :: Set a -> [a] -> [a]
loop Set a
_    []            = []
          loop Set a
seen (a
x : [a]
xs)
              | a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
member a
x Set a
seen = Set a -> [a] -> [a]
loop Set a
seen [a]
xs
              | Bool
otherwise         = a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: Set a -> [a] -> [a]
loop (a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
insert a
x Set a
seen) [a]
xs


-- | Replace all occurences of an element by another element.
replace :: Eq a => a -> a -> [a] -> [a]
replace :: a -> a -> [a] -> [a]
replace a
x a
y = (a -> a) -> [a] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map (\a
z -> if a
z a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
x then a
y else a
z)