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

On Fri, Nov 18, 2011 at 9:16 AM, Roman Cheplyaka wrote:

* 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)

"it's not" as in "it's not documented".

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

Good point. I will mull this over. -- Johan