cost of List.// for Ord types?
Hello, I was wondering if the list diff operator \\ takes advantage of situations where the list data type is in class Ord, besides being in Eq. If it is only in Eq, then \\ must be O(n^2), while if it is in Ord, a O(nlogn) \\ can be written. Basically, I'm wondering if I should avoid using the standard library \\, and if so, whether there might be some better solution than writing my own (which would involve sorting the lists, and then the obvious picking off of the appropriate values). If there isn't a \\ that takes advantage of Ord, could there be? This being a more fundamental question: can you write a separate version of a function for the case where its argument is within a more specific class? -- David Roundy http://www.abridgegame.org
On Fri, 3 Sep 2004, David Roundy wrote:
Hello,
I was wondering if the list diff operator \\ takes advantage of situations where the list data type is in class Ord, besides being in Eq. If it is only in Eq, then \\ must be O(n^2), while if it is in Ord, a O(nlogn) \\ can be written.
Is it a problem that can also be solved by a more sophisticated data structure like FiniteMap?
On 03-Sep-2004, David Roundy
I was wondering if the list diff operator \\ takes advantage of situations where the list data type is in class Ord, besides being in Eq.
No, it cannot, at least not in the general case. The interface for "\\" says that it only depends on the Eq class; calling Ord member functions would not have the right semantics.
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. -- Fergus J. Henderson | "I have always known that the pursuit Galois Connections, Inc. | of excellence is a lethal habit" Phone: +1 503 626 6616 | -- the last words of T. S. Garp.
Fergus Henderson
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
participants (4)
-
David Roundy -
Fergus Henderson -
Henning Thielemann -
Ketil Malde