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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
