Unique elements, long runtime Haskell

Question

I have two functions. Both have to have unique elements, one with Integers and the other a String which returns a list of Char. My runtime is currently quite high and I'm not allowed to use imports, but I was wondering how to improve them:

uniqueInt:: [Int] -> [Int]
uniqueInt[] = []
uniqueInt xs = [x | (x,y) <- zip xs [0..], x `notElem` (take y xs)]

Example: uniqueInt [1,2,1,3,1,2] = [1,2,3]

uniqueString :: String -> [Char]
uniqueString ""=[]
uniqueString xs = [x | (x,y) <- zip xs [0..], x `notElem` (take y xs)]

Example: uniqueString "hello"="helo"

Answer 1

Firstly you might want to make use of a Haskell feature to combine both functions into one:

unique :: Eq a => [a] -> [a]
unique [] = []
unique xs = [x | (x,y) <- zip xs [0..], x `notElem` (take y xs)]

Now let's talk about performance. Obviously lists aren't great in this respect, since take is quite expensive and needs to iterate through the list, as well as notElem, which will, again iterate through the list. Plus this is also constructing new lists, which leads to GC, which leads to decreased performance.

So best option would be to go through the list only once, putting each element into a set while it's then only collecting the elements which haven't been in the set yet at that moment.

That's of course a very imperative way of doing it. And regardless, if you're not allowed to use imports you'd have to create the respective data structures yourself, which I'd say isn't worth the effort.

---

In any case, at least within the constraints set it's still possible to make this a bit more efficient, basically by copying nub's implementation:

unique :: Eq a => [a] -> [a]
unique l = unique' l []
  where
    unique' [] _ = []
    unique' (x:xs) ls
           | x `elem` xs = unique' xs ls
           | otherwise   = x : unique' xs (x:ls)