As noted, (Data.Set.toList . Data.Set.fromList) is the best traditional
solution if you don't care about order (or Data.Set.toAscList for a
sorted result).
If order is important, the new bijective Data.Bimap class
http://code.haskell.org/~scook0/haddock/bimap/Data-Bimap.html
may be your best bet (I haven't yet tried it myself).
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
There is a hidden proof obligation here:
Exercise: Prove that (groupBy equalFsts >>> map head) is a total
function, using the defintion of groupBy from Data.List:
groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy _ [] = []
groupBy eq (x:xs) = (x:ys) : groupBy eq zs
where (ys,zs) = span (eq x) xs
Felipe Lessa wrote:
2008/2/8 Jed Brown <[EMAIL PROTECTED]>:
Look at Data.List:
nub :: (Eq a) => [a] -> [a]
nub = nubBy (==)
nubBy :: (a -> a -> Bool) -> [a] -> [a]
nubBy eq [] = []
nubBy eq (x:xs) = x : nubBy eq (filter (\ y -> not (eq x y)) xs)
And then there's also
sort :: (Ord a) => [a] -> [a]
which should have better performance, O(n log n) against O(n²) I
guess, but of course will change the order of the elements. If you
really don't mind the order at all, you could also use Data.Set in the
first place.
Cheers,
------------------------------------------------------------------------
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
