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

Henning Thielemann iakd0 at clusterf.urz.uni-halle.de
Tue Sep 7 04:08:21 EDT 2004


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?



More information about the Haskell-Cafe mailing list