[Haskell-cafe] Edison StandardSet has inefficient function implementation

Ahn, Ki Yung kyagrd at gmail.com
Thu Aug 3 07:14:04 EDT 2006

Edision does not yet have all the asymtotic description of its functions.
I got the Edision 1.2 source and looked into the code whether the
container implementations meet the expected asymtotic bounds.

In the module Data.Coll.StandardSet which packages Data.Set,
some functions which can be O(log n) is implemented as O(n).

Data.Set has a split and splitMember running in O(log n).
With those functions we can implement OrdCollX operations like
filterLT, filterLE, filterGT, filterGE,
partitionLT_GE, partitionLE_GT, partitionLT_GT all in O(log n).
However, only partitionLT_GT was O(log n) implemended using split.
All other function implmentation just used its axiomaic description
using CollX operations like filter and partition, which is O(n).

It needs to be fixed.

P.S. I haven't checked the darcs version yet.

Ahn, Ki Yung

More information about the Haskell-Cafe mailing list