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

Ross Paterson ross at
Fri Jan 14 12:04:01 CET 2011

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

More information about the Libraries mailing list