module Autolib.Util.Uniq where

-- -- $Id$

import Autolib.Set

-- | produce a lazy (!) sublist of entries with all duplicates removed
uniq :: Eq a => [a] -> [a]
uniq :: forall a. Eq a => [a] -> [a]
uniq [] = []
uniq (a
x : [a]
xs) = a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
filter ( a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
x ) ( [a] -> [a]
forall a. Eq a => [a] -> [a]
uniq [a]
xs )

-- | produce a lazy (!) sublist of entries with all duplicates removed
-- use a Set to cache the entries already seen
uniqs :: Ord a => [a] -> [a]
uniqs :: forall a. Ord a => [a] -> [a]
uniqs [a]
xs = Set a -> [a] -> [a]
forall {a}. Ord a => Set a -> [a] -> [a]
helper Set a
forall {a}. Set a
emptySet [a]
xs where
    helper :: Set a -> [a] -> [a]
helper Set a
done [] = []
    helper Set a
done ( a
x : [a]
xs ) = 
	   if a -> Set a -> Bool
forall {a}. Ord a => a -> Set a -> Bool
elementOf a
x Set a
done
	   then Set a -> [a] -> [a]
helper Set a
done [a]
xs
	   else a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: Set a -> [a] -> [a]
helper ( Set a -> a -> Set a
forall {a}. Ord a => Set a -> a -> Set a
addToSet Set a
done a
x ) [a]
xs