Efficent lens operation for Data.Map et al.

[Roman Cheplyaka]

* roconnor at theorem.ca <roconnor at theorem.ca> [2012-01-18 19:26:02-0500]
> On Wed, 18 Jan 2012, Johan Tibell wrote:
> 
> >On Wed, Jan 18, 2012 at 1:51 PM, Roman Cheplyaka <roma at ro-che.info> wrote:
> >>* roconnor at theorem.ca <roconnor at theorem.ca> [2012-01-18 16:35:52-0500]
> >>>On Wed, 18 Jan 2012, Johan Tibell wrote:
> >>>
> >>>>IIRC you just replace the current functions with yours and run make in
> >>>>the benchmarks/ directory to compile the benchmark binaries (which use
> >>>>Criterion). Then simply run them.
> >>>
> >>>I got an error trying to build the benchmarks:
> >>
> >>Worked for me with GHC 7.0.4.
> >>
> >>The results are attached.
> >>
> >>In short, your version is indeed typically slower, up to a factor of 5
> >>(for lookup).
> >
> >That's even slower than I expected. Doesn't mean that we cannot add
> >the operation though (although we should think about exactly which
> >operation(s) we need.)
> 
> Ya, all I really want is one function:
> 
> lens :: Key -> IntMap a -> (Maybe a -> IntMap a, Maybe a)
> 
> for every container type.

Considering the benchmark results, it seems that implementing lens
in terms of lookup and update actually is the fastest option we've seen?

The difference between one and two traversals could become significant
as the tree depth increases, but:

* for Data.{Map,Set} it's logarithmic in the container
  size, so it won't be large for something that fits into memory

* for Data.Int{Map,Set} it's bounded by the size of Int

-- 
Roman I. Cheplyaka :: http://ro-che.info/