Proposal: keep Data.Map.foldWithKey

[Johan Tibell]

On Fri, Dec 17, 2010 at 8:45 AM, Max Bolingbroke
<batterseapower at hotmail.com> wrote:
> On 16 December 2010 23:04, Ross Paterson <ross at soi.city.ac.uk> wrote:
>> Well, once you have
>>
>>  withKeys :: Map k a -> Map k (k,a)
>>  withKeys = mapWithKey (,)
>>
>> and the Foldable instance, all those fold variants are redundant, as are
>> all the WithKey variants.
>
> Not as efficient though, because using withKeys and then folding
> requires two traversals and allocates an intermediate map compared to
> just folding withKey.

One could try to separate traversal from combining the elements using
using toList and e.g. Data.List.foldl', assuming Data.List was
implemented using stream fusion. I think this would be an interesting
experiment to run.

> More broadly, I don't really see the argument for removing stuff from
> Data.Map. The code is already written and the core implementation of
> Data.Map is unlikely to change very much since Milan already confirmed
> it's almost optimal. So there doesn't seem to be a big maintainer
> burden to keeping the current interface. Is there some reason that
> maintaing Data.Map is more difficult than I expect?

Actually there's more work to do on Data.Map (and the other modules as
well). For example, the 6 adjust*, update*, and alter functions are
all non-strict and thus mostly useless (i.e. you rarely want to leave
thunks in the map.) To address this problem we would have to add
strict versions of (some of them). I just noticed that we're missing
strict folds as well (I thought we added those) so those need to be
added as well. There are a bunch of other high-order functions that
might need strict versions as well.

Given that we have to add a load of function to make the API usable
for e.g. keeping a simple map of strings to integer counters, I'd like
to see if we can counterbalance that growth by removing something.
There are a bunch of functions of dubious value (i.e. don't add
expressiveness or performance). The old foldWithKey was one of them,
but there are others such as findWithDefault, (!), etc.

There's also an overhead in creating and running tests/benchmarks for
all these functions.

> There may be a burden to the new user of Data.Map if they are
> overwhelmed by the sheer number of different functions (though this is
> not a problem I had personally), but that could be solved by having a
> Data.Map.Simple module or just reorganising the Haddock docs so the
> most commonly used functions appear first on the page. Is this not a
> better approach than breaking existing code by removing functionality?

Perhaps, the Haddock docs could need an overhaul for sure. I don't
argue for removing "functionality", just removing things from the API
that don't really add any expressiveness or performance.

Cheers,
Johan