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

[Ross Paterson]

On Fri, Jan 14, 2011 at 11:58:18AM +0100, Johan Tibell wrote:
> 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?

That's essentially apfelmus's original suggestion.  I believe I tried
that but creating the closures seems even slower.