Re: Proposal: keep Data.Map.foldWithKey

On Fri, Dec 17, 2010 at 8:45 AM, Max Bolingbroke wrote:

On 16 December 2010 23:04, Ross Paterson 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