[Haskell-cafe] cost of List.// for Ord types?
ketil+haskell at ii.uib.no
Wed Sep 8 02:45:04 EDT 2004
Fergus Henderson <fjh007 at galois.com> writes:
>> Basically, I'm wondering if I should avoid using the standard library \\,
> If efficiency is a significant concern, and the lists involved may be long,
> yes, you should.
I'm not sure how to preserve the semantics, either. (\\) seems to
delete the first occurence of every value in the second list. I first
(\\\) :: Ord a => [a] -> [a] -> [a]
a \\\ b = setToList $ minusSet (mkSet a) (mkSet b)
and while it's often what I want, it's clearly not the same thing.
More accurate to build a frequency table with
freq xs = addListToFM_C (+) emptyFM $ zip xs $ repeat 1
and traverse the input something like (untested):
a \\\ b = let ft = freq b in delf ft b
delf ft (x:xs) = case lookupFM ft x of
Nothing -> x : delf ft xs
Just n -> delf (addToFM ft x (n-1)) xs
delf _  = 
Should be O(|a|+|b|log|b|), I think.
If I haven't seen further, it is by standing in the footprints of giants
More information about the Haskell-Cafe