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

[Johan Tibell]

On Fri, Nov 18, 2011 at 9:16 AM, Roman Cheplyaka <roma at ro-che.info> wrote:
> * Johan Tibell <johan.tibell at gmail.com> [2011-11-18 08:06:29-0800]
>> On Fri, Nov 18, 2011 at 12:09 AM, Roman Cheplyaka <roma at ro-che.info> 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