Re: mkSet on sorted lists

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 difficult.

Wolfgang

Best regards, Tom -- .signature: Too many levels of symbolic links