Re: [Haskell-cafe] Documenting strictness properties for Data.Map.Strict

* Johan Tibell [2011-11-18 08:06:29-0800]

On Fri, Nov 18, 2011 at 12:09 AM, Roman Cheplyaka wrote:

...

Is it mentioned anywhere that Map is spine-strict?

It's not and we should probably mention it.

Hm. Perhaps I'm missing something, but data Map k a = Tip | Bin {-# UNPACK #-} !Size !k a !(Map k a) !(Map k a) looks pretty (spine-)strict to me. (This is in the latest rev from http://github.com/haskell/containers.git)

I was mulling this over last night. My initial thought was that it shouldn't matter as long as the algorithmic complexity of the functions is maintained. But it is important in that a lookup following an insert might do all the work of the insert, which is somewhat surprising (and inefficient).

It's also space and "stack" complexities that matter (not sure if you include those in algorithmic complexity). For example, if it's not spine-strict, then Map.lookup k $ foldl' Map.union Map.empty longList would overflow the stack despite the prime in foldl'. -- Roman I. Cheplyaka :: http://ro-che.info/