Re: [Haskell-cafe] (no subject)

Jake McArthur wrote:

staafmeister wrote:

...

Yes I know but there are a lot of problems requiring O(1) array updates so then you are stuck with IO again

Or use ST. Or use IntMap (which is O(log n), but n is going to max out on the integer size for your architecture, so it's really just O(32) or O(64), which is really just constant time).

Actually, IntMap is O(min(n,W)) where W is the number of bits in an Int. Yes, IntMaps are linear time in the worst case (until they become constant-time). In practice this is competitive with all those O(log n) structures though. Whereas Data.Map is O(log n) for the usual balanced tree approach. -- Live well, ~wren