[Haskell-cafe] Create a list without duplicates from a list with duplicates

[Tillmann Rendel]

Dan Weston wrote:
> Meanwhile, here is a hand-rolled solution to order-preserving nubbing:
> 
>  > import Data.List(groupBy,sortBy,sort)
>  > import Data.Maybe(listToMaybe)
>  >
>  > efficientNub :: (Ord a) => [a] -> [a]
>  > efficientNub  = flip zip [0..]        -- carry along index
>  >             >>> sort                  -- sort by value, then index
>  >             >>> groupBy equalFsts     -- group adjacent equal values
>  >             >>> map head              -- keep only primus inter pares
>  >             >>> sortBy compareSnds    -- sort by index
>  >             >>> map fst               -- discard index
>  >
>  >   where equalFsts   (x1,y1) (x2,y2) = x1 == x2
>  >         compareSnds (x1,y1) (x2,y2) = compare y1 y2
>  >         x >>> y = y . x

I would try something like

   efficientNub = catMaybes . snd . mapAccumR f empty where
     f s x | member x s = (s, Nothing)
           | otherwise = (insert x s, x)

that is, threading the Set of already given results through.

   Tillmann