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 wouldhave 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 alazy 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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
smime.p7s
Description: S/MIME cryptographic signature
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
