On Fri, Nov 18, 2011 at 9:16 AM, Roman Cheplyaka <r...@ro-che.info> wrote:
> * Johan Tibell <johan.tib...@gmail.com> [2011-11-18 08:06:29-0800]
>> On Fri, Nov 18, 2011 at 12:09 AM, Roman Cheplyaka <r...@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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
