Linear time IntSet / IntMap construction from sorted input

[Duncan Coutts]

On Wed, 2008-05-21 at 14:20 -0600, Scott Dillard wrote:
> I got an off-list response from Bertram Felgenhauer, and he made some
> improvements to my code. I've attached a new patch -- disregard the
> old one.
> 
> Here are the timings on my 2Ghz Core Duo, for the program
> 
> main = print . IS.fold (+) 0 . IS.fromList $ [i-n|i<-[1..2*n]] where n = 5000000
> 
> original:
> 2,820,354,288 bytes allocated in the heap
>   Total time    5.19s  (  5.47s elapsed)

> new function:
> 1,168,348,000 bytes allocated in the heap
>   Total time    3.63s  (  3.93s elapsed)

> How many times can I reply to myself before I'm banned from the
> list? :)

As many as you like if you keep posting improvements like that! :-)

Duncan