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

[Johan Tibell]

On Fri, Jan 14, 2011 at 11:06 AM, Ross Paterson <ross at soi.city.ac.uk> wrote:
> I've also had no success in speeding it up.  It's disappointing that
> having the extra information (whether the key was there or not) doesn't
> help, but I think I agree.

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?

Johan