Unique elements, long runtime Haskell 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] -&gt; [Int]
uniqueInt[] = []
uniqueInt xs = [x | (x,y) &lt;- zip xs [0..], x `notElem` (take y xs)]

Example:
uniqueInt [1,2,1,3,1,2] = [1,2,3]
uniqueString :: String -&gt; [Char]
uniqueString &quot;&quot;=[]
uniqueString xs = [x | (x,y) &lt;- zip xs [0..], x `notElem` (take y xs)]

Example: uniqueString &quot;hello&quot;=&quot;helo&quot;
Firstly you might want to make use of a Haskell feature to combine both functions into one:
unique :: Eq a =&gt; [a] -&gt; [a]
unique [] = []
unique xs = [x | (x,y) &lt;- 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 =&gt; [a] -&gt; [a]
unique l = unique' l []
  where
    unique' [] _ = []
    unique' (x:xs) ls
           | x `elem` xs = unique' xs ls
           | otherwise   = x : unique' xs (x:ls)