[Haskell-cafe] function result caching
jmaessen at alum.mit.edu
Fri Oct 13 08:52:09 EDT 2006
On Oct 13, 2006, at 4:05 AM, Tomasz Zielonka wrote:
> On Thu, Oct 12, 2006 at 08:40:44PM -0700, John Meacham wrote:
>> it is too bad IntSet and IntMap are strict in their subtrees, it
>> have been nice to provide things like
>> out of curiosity, why are IntMap and IntSet strict in their subtrees.
> I guess the reason is balancing. I can't think of any way of
> balancing a
> lazy tree that wouldn't break abstraction.
Uh, Patricia trees aren't balanced in the usual sense. There is
exactly one tree structure for a given set of keys, regardless of
insertion order etc. (IntSet and IntMap workes approximately as Carl
Witty described last I checked, though I won't swear to whether bits
are taken low to high or vice versa.)
I had assumed the strictness was to avoid deferring O(n) insertion
work to the first lookup operation---though really it makes no
difference in an amortized sense.
> Perhaps I would be possible to use some trick to rebalance an existing
> tree to account for what's currently evaluated. But it could be very
> tricky to get it right and it would certainly go beyond Haskell 98.
> Best regards
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 2425 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20061013/5a5739f6/smime-0001.bin
More information about the Haskell-Cafe