* 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)
> 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/
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
