Unique elements of a list and corresponding indices in Haskell
Various Comments

First, Stack Exchange sent the body of my response into the void when I logged in to post it, so I'm going to be a bit more brief and a bit less organized than I originally wanted because I'm lazy.

This is not really reviewing your code, so it would've been better served as a comment, but I didn't think to comment my approach before I wrote out all the code. Might as well share it in case it's helpful. 

To be honest, I don't quite understand your second solution, but on a second read it looks like it might still be n^2 (same asymptotic complexity as your first solution), so that would explain why it's slower. I assumed at first it was just something to do with mutability and vectors (which I don't really understand myself), but on second read I'm no longer so sure about this.

If you don't mind me being frank in answering your first question: I don't really think it's nice. I had a pretty rough time reading it, to the point where I instead just wrote a more Haskell-inclined solution that has better asymptotic performance than your first one.

Proposed Solution

Are you okay with an n log n solution? If memory serves, with the right choice of set/map, the log's base is so large that it is effectively linear.

Here is one such solution

import Data.List (foldl', sortOn)
import Data.Map (Map)
import qualified Data.Map as Map

-- | Gives the unique elements of 'elems' in order.
orderedNub :: Ord a =&gt; [a] -&gt; [a]
orderedNub elems = sortOn (firstIndexMap Map.!) (Map.keys firstIndexMap)
  where
    -- Insert such that if the value is already in 'firstIndexMap', it is not
    -- updated.
    addElem m (elem, index) = Map.insertWith (flip const) elem index m
    -- Left fold in order to get the first occurance of each element.
    firstIndexMap = foldl' addElem Map.empty $ zip elems [0..]

-- | Gives the unique elements of 'elems' and the indices of 'elems' in
-- the unique list of elements.
unique :: Ord a =&gt; [a] -&gt; ([a], [Int])
unique elems = (uniques, indices)
  where
    uniques = orderedNub elems
    uniqueInds = zip uniques [0..]
    indexMap = foldr (uncurry Map.insert) Map.empty uniqueInds
    -- We can use unsafe indexing since we know that 'indexMap' has
    -- the right values.
    indices = [indexMap Map.! x | x &lt;- elems]


Some Notes About the Solution


I changed the code so it is correct now, assuming you want to preserve order. Some of these comments may be a bit out of date as a result.
orderedNub' is a kind of clunky definition, but it should have better asymptotic performance than nub. I’m pretty sure you can avoid the overhead of an actual sort (one clunky way would be to use a vector like you’re using).
uncurry Map.insert is a cute pointfree thing, if that's not your dig just sub it with a lambda or helper function.
I can't think of a good way to avoid using Map.!, even though it's partial. If I used Map.lookup, then there'd have to be a fromJust or a Maybe overhead, even though the map is, by construction, going to have the right keys. Guess this is a shortcoming of the type system.