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