# Linear time IntSet / IntMap construction from sorted input

Scott Dillard sedillard at ucdavis.edu
Mon May 19 19:43:47 EDT 2008

```Hi,

It's always bugged me that IntSet.fromAscList is an alias for
fromList, which is basically (foldr insert), even though a sorted list
is (almost) already in tree order. Is there a reason for this? Or was
it just that fromList is good enough? (which it is.)

Assuming the latter, and somewhat bored, I wrote a function to build
an IntSet from sorted input in linear time. This goes in
Data.IntSet.hs :

data Stack = Push {-# UNPACK #-} !Prefix !IntSet !Stack | Nada

fromAsc xs = make Nada xs
where
make stk []      = finish stk
make Nada (z:zs) = make (Push z (Tip z) Nada) zs
make stk@(Push _ y Nada) (z:zs)  = make (Push z (Tip z) stk) zs
make stk@(Push py y stk') zs@(z:zs') =
make (Push z (Tip z) (reduce (branchMask py z) stk)) zs'

reduce _ stk@(Push _ x Nada) = stk
reduce m stk@((Push px x (Push py y stk'))) =
let !mxy = branchMask px py
!pxy = mask px mxy
in  if shorter m mxy
then reduce m (Push pxy (Bin pxy mxy y x) stk')
else stk

finish Nada = Nil
finish (Push _ x Nada) = x
finish (Push px x (Push py y stk)) = finish (Push p (join px x py y) stk)
where m  = branchMask px py
p  = mask px m

Every trie node is allocated exactly once, and so the burden on the
heap is significantly less, even if its only a little bit faster. I
tested it by building a list from -n to n for big n, and computing the
sum. It alloc's 50% less and the MUT time is like 40% less, but the GC
time is more (why would that be?) so it runs in maybe 7/8ths the time,
versus fromList.

I have another, prettier version that uses [] instead of this hacky
Stack type, but its slower, breaking even with fromList on speed,
still allocating much less.

Is this something you guys feel would be worth including? Should I
make a proper patch? One could even use this to write an O(n)
mapKeysMonotonic, bringing the IntMap and Map APIs further into
alignment. Or is 8/7x speedup not worth the extra code weight?

Scott
```