Opened 9 years ago

Closed 9 years ago

#4313 closed proposal (invalid)

Proposal: Add left, right and strict folds to Data.Set, Data.IntMap and Data.IntSet to mimic Data.Map.

Reported by: milan Owned by:
Priority: normal Milestone: Not GHC
Component: libraries (other) Version: 6.12.3
Keywords: containers Cc: johan.tibell@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: #4278, #4280 Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

This proposal depends on #4278 and #4280.

In accordance with a poll on libraries@… (see point 3 of http://article.gmane.org/gmane.comp.lang.haskell.libraries/13273) I propose to add strict folds to the containers.

The Data.Map is getting left, right and strict folds in #4278. This proposal adds left, right and strict folds for Set, IntMap and IntSet.

The naming is a bit tricky. The folds in IntMap mimics Map (ie. foldrWithKey, foldlWithKey, foldlWithKey'; fold and foldWithKey are deprecated in favor of foldrWithKey). The folds in Set and IntSet are classic (foldr, foldl, foldl'; the old fold is deprecated in favor of foldr).

The repository of the containers package with these patches (and also several others) is at http://fox.auryn.cz/darcs/containers/.

The patches are also attached (including #4280).

Attachments (1)

containers-folds.patch (25.5 KB) - added by milan 9 years ago.

Download all attachments as: .zip

Change History (9)

Changed 9 years ago by milan

Attachment: containers-folds.patch added

comment:1 Changed 9 years ago by tibbe

Cc: johan.tibell@… added

I think we should have both strict left and right folds, not just strict left folds.

comment:2 in reply to:  1 Changed 9 years ago by milan

Replying to tibbe:

I think we should have both strict left and right folds, not just strict left folds.

I made the patch to mimic Data.Map.

But I agree, we should add right strict fold.

We could also add foldl, foldr, foldl' and foldr' to Data.Map and Data.IntMap (currently only the *WithKey are present), but I do not feel strongly either way.

comment:3 Changed 9 years ago by tibbe

I'd be against adding both the value-only and key/value folds. In fact I think we should only have the key/value folds as they are as efficient as the value-only folds. Having both bloats the API. It's already bloated as is.

comment:4 in reply to:  3 Changed 9 years ago by milan

Replying to tibbe:

I'd be against adding both the value-only and key/value folds. In fact I think we should only have the key/value folds as they are as efficient as the value-only folds. Having both bloats the API. It's already bloated as is.

Fine by me.

BTW, I just found out that the order of foldlWithKey is inconsistent: Data.Map.foldlWithKey :: (b -> k -> a -> b) -> b -> Map k a -> b Data.IntMap.foldlWithKey :: (Key->b -> a -> b) -> b -> IntMap a-> b

I like that the Data.IntMap variant works well with 'const' to produce foldl. But the order of the parameters is a bit illogical then.

Any suggestions?

comment:5 Changed 9 years ago by milan

We are now waiting for the performance patches to settle in first.

The repository http://fox.auryn.cz/darcs/containers/ does not contain the fold patches now.

comment:6 Changed 9 years ago by igloo

Milestone: Not GHC

comment:7 Changed 9 years ago by maeder

Type: taskproposal

I wondered why this ticket was not listed as proposal

comment:8 Changed 9 years ago by igloo

Resolution: invalid
Status: newclosed

Proposal tickets are no longer needed as part of the library submissions process. Instead, a normal ticket should be created once consensus has been achieved. Please see the process description for details.

Note: See TracTickets for help on using tickets.