[Haskell-cafe] Re: Optimization problem

[apfelmus at quantentunnel.de]

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