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

David Roundy droundy at droundy.dyndns.org
Fri Sep 3 07:27:11 EDT 2004


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

More information about the Haskell-Cafe mailing list