Ross Paterson wrote: > On Sun, Sep 17, 2006 at 01:08:04PM +0200, [EMAIL PROTECTED] wrote: >> Ross Paterson wrote: >>> It's interesting that these composed transformations don't seem to cost >>> too much. >> That the composed transformations are indeed cheap is not necessarily >> disturbing. > > I meant the composition of the transformations of the tree (update or > reverse insert) that Bertram does for each list element. They're cheap > because they're bounded by the depth of the tree, and even cheaper if > you're probing some other part of the tree.
Me too :) I tried to point out that separating uninsert from in insert increases time complexity. In general uninsert :: Ord k => k -> Map k () -> Map k a -> (a, Map k a) fst $ uninsert _ bp m == differenceWith (curry snd) bp m with needs O(size of blueprint) time. This is to be compared with O(log (size of blueprint)) for the combined insertdelete. That there (likely) must be such a difference can already be seen from the types of insertdelete and (insert,uninsert) ! But you already pointed out that something like insertdelete :: Ord k => k -> Map shape k -> (exists shape' . (Map shape' k, Map shape' a -> (a, Map shape a)) is the best type for insertdelete. Here, it is clear that insertdelete likely can do a fast uninsert. Btw, why are there no irrefutable patterns for GADTs? I mean, such a sin should be shame for a non-strict language... Regards, apfelmus _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe