Library proposal: add a Location interface for element-wise operations on Data.Map (#4887)

[Jan-Willem Maessen]

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
flexibly).

Remember that a closure (especially a complex continuation) is *also*
a data structure, folks!

-Jan