mkSet on sorted lists

Tomasz Zielonka t.zielonka at
Wed Jan 7 19:30:35 EST 2004

On Wed, Jan 07, 2004 at 05:41:04PM +0100, Wolfgang Jeltsch wrote:
> Hello,
> does Data.Set.mkSet run in linear time when applied to a sorted list?

No, at least not in the version from GHC 6.0. This implementation is
based on FiniteMap. mkSet translates to listToFM, which incrementally
constructs the result map using foldl on the input list.

Hmmm, I may try to fix it in a day or two... it shouldn't be too

> Wolfgang

Best regards,

.signature: Too many levels of symbolic links

More information about the Haskell mailing list