[Haskell-cafe] function result caching

[Jan-Willem Maessen]

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  
>> would
>> 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.

-Jan-Willem Maessen

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2425 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20061013/5a5739f6/smime-0001.bin