Ross Paterson wrote:
On Sun, Sep 17, 2006 at 01:08:04PM +0200, apfelmus@quantentunnel.de 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