Library proposal: add a Location interface for element-wise operations on Data.Map (#4887)
jmaessen at alum.mit.edu
Sun Jan 16 05:15:54 CET 2011
On Fri, Jan 14, 2011 at 6:04 AM, Ross Paterson <ross at soi.city.ac.uk> wrote:
> On Fri, Jan 14, 2011 at 11:58:18AM +0100, Johan Tibell wrote:
>> ...[Ross couldn't speed things up easily.]
>> I think the problem is that you get almost 2x allocation. O(log n)
>> allocation to create the Path and O(log n) allocation to rebuild the
>> tree. Perhaps one could use continuations to create the whole instead
>> of reifying the stack as a Path? We might lose the ability to get the
>> smaller/larger elements but at least we might be able to update the
>> "hole" efficiently?
> That's essentially apfelmus's original suggestion. I believe I tried
> that but creating the closures seems even slower.
Er, yes, the proposed data structure defunctionalizes these
continuations (which in principle also lets us manipulate them more
Remember that a closure (especially a complex continuation) is *also*
a data structure, folks!
More information about the Libraries