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

[Roman Cheplyaka]

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

> 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/