[Haskell-cafe] cost of List.// for Ord types?

[Ketil Malde]

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
tried this

  (\\\) :: 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.

-kzm
-- 
If I haven't seen further, it is by standing in the footprints of giants