Hi, sorry for breaking the rules again and not making myself clear. I would like to hear other opinions on the folds in the containers package. The Set, and IntSet have one 'fold' that does not specify order of folding (but in fact are right folds). Map and IntMap have 'fold' and 'foldWithKey' which is a right fold (and documented as such). Recently foldrWithKey and foldlWithKey was added to Data.Map (foldWithKey is deprecated and a synonymous for foldrWithKey). There are two thinks I am thinking about: a) add left/right folds, b) add strict folds. What do you think about: a) add foldrWithKey and foldlWithKey to IntMap, make foldWithKey deprecated and synonymous for foldrWithKey. b) add foldl and foldr to Set and IntSet, make fold deprecated and synonymous to foldr. c) add strict variants of left and right folds, namely Data.Map, Data.IntMap: foldlWithKey' foldrWithKey' Data.Set, Date.IntSet: foldl', foldr' Some issues: - should fold be really renamed to foldr? Maybe we could clarify that fold and foldWithKey are right folds and add only foldl and foldlWithKey. - should fold really be deprecated? It could break a lot of code. - adding foldl, foldr, foldl' and foldr' to Set and IntSet is going to cause a lot of trouble because of shadowing. Maybe some better name? On the other hand, these are the "right" names. Thanks for any opinions. Milan

On 9/24/10 1:45 PM, Thomas Schilling wrote:

Regarding the questions: I prefer the foldr/l names, because otherwise I may need to look up the documentation to figure out which fold it is. It's much better to use the standard naming convention from lists. As an example, there is foldM which is actually a left fold. Data.Foldable fixes this and only uses the generic name 'fold' for the Monoid case where order does indeed not matter due to associativity of mappend.

I agree with both parts of this. That is, foldr/l are the best names for when the order is specified. However, sometimes we do have an associative operator and don't care about the order. In these latter cases I think it's best to offer a "fold" which doesn't specify order in order to prevent client code from over-specifying what they mean. Also, having an order-independent fold allows the library to choose whatever kind of fold would be most efficient (possibly changing it over time), and allows for things like a parallel implementation for overcoming the "fold considered harmful"[1] problem. [1] http://vidiowiki.com/watch/p92te4e/Guy_Steele_foldl_and_foldr_considered_sli... -- Live well, ~wren

On Friday 24 September 2010 22:20:56, Johan Tibell wrote:

On Fri, Sep 24, 2010 at 7:09 PM, Milan Straka wrote:

...

There are two thinks to sort out: a) add left/right folds, b) add strict folds.

I therefore propose to: a) add foldrWithKey and foldlWithKey to IntMap, make foldWithKey deprecated and synonymous for foldrWithKey.

+1

ditto

...

b) add foldl and foldr to Set and IntSet, make fold deprecated and synonymous to foldr.

+1

ditto

...

c) add strict variants of left and right folds, namely Data.Map, Data.IntMap: foldlWithKey' foldrWithKey' Data.Set, Date.IntSet: foldl', foldr'

+1

ditto

...

Some issues: - should we really rename fold -> foldr? Maybe we could cla that fold and foldWithKey are right folds and add only foldl and foldlWithKey.

I'd prefer to rename. We need to keep the old version around for a long time though, with a DEPRECATED pragma encouraging people to upgrade.

I heartily agree.

...

- should we really deprecate fold and foldWithKey? It could break a lot of code.

I think so. Give people a year or so to move over.

I agree here also.

...

- adding foldl, foldr, foldl' and foldr' to Set and IntSet is going to cause a lot of trouble because of shadowing. Maybe some better name? On the other hand, these are the "right" names.

I think we should go with the "right" names. I think many modules already import these modules qualified due to other name clashes (as they should). We should encourage proper use of namespaces to resolve name clashes. Breakages can be resolved by putting a upper version bound on containers in the .cabal file of the broken library.

And here too.

-- Johan

Cheers, Daniel

On Fri, Sep 24, 2010 at 10:51 PM, Thomas Schilling wrote:

On 24 September 2010 21:20, Johan Tibell wrote:

...

...

- should we really deprecate fold and foldWithKey? It could break  a lot of code.

I think so. Give people a year or so to move over.

I'd prefer two years.  Not everyone is moving as quickly as GHC, and containers is a core library.

An alternative would be to see how many hackage libraries would build after e.g. one year if we removed the function. If there are any, wait some more, if there are few, remove the functions. I picked one year as that's equivalent to two HP releases.

On Sat, Sep 25, 2010 at 03:41:53PM +0200, Johan Tibell wrote:

On Sat, Sep 25, 2010 at 2:41 PM, Ian Lynagh wrote:

...

Why not also add foldl and foldr to Map and IntMap, and deprecate fold?

I think having all these with and without key version of all the functions in Data.{Map,Set} is a misstake. They don't improve performance (I've checked) and they almost double the size of the API (which is a whopping ~150 functions!).

It does add a load more functions, but not much cognitive overhead. In fact, I think users will find it easier if the simpler functions they are used to from other type (e.g. [], Set) exist. The WithKey functions are also klunkier to use if you don't need the key, especially if you are using them in a point-free style (e.g. if you're mapping or folding with them).

* I'm working on a tool to check all of Hackage for use sites of particular functions. If that tool shows that no one uses some of these functions, we could consider removing them.

Yes, it would be very useful to see how many uses there are of the WithKey functions vs the keyless functions. It may also be interesting to see how many of the WithKey calls ignore the key. Thanks Ian