export toDescList from Data.Map

newer
Proposal (Trac ticket #3671): Add...

Evan Laforge

8 Sep 2008 8 Sep '08

6:46 p.m.

So, I mentioned this a long time ago but didn't get any responses and then I got distracted. So this time I added a ticket and patch and everything: 2580 Here's the text: It's even implemented, but not exported. Without this, there's apparently no way to iterate over a map from high to low, since foldl is also not exported. Also, I implemented a toDescList for IntMap, and could do the same for Set, and could add those patches, if people agree it's a good idea. In addition, is there any problem with exporting foldl aka descending for the three modules? I implemented a foldl for IntMap and it seems to work, but I'd want someone smarter to look for problems with it. In addition, Set and Map are inconsistent with folds: Set exports 'fold' and says "no order is guaranteed", but it's just defined to foldr, which is in ascending order. Set.foldr itself is not exported. Meanwhile, Map also exports fold, but heavily implies from the doc that it's guaranteed to be ascending. Would it restrict implementation changes too much to export a descending fold for all three? Other languages that have tree oriented general purpose maps all let you start anywhere and iterate in either direction. Anyway, is 2-3 weeks ok for discussion period? The library submission wiki doesn't say how long.

Show replies by date

Benedikt Huber

10 Sep 10 Sep

2:06 p.m.

Evan Laforge schrieb:

...

So, I mentioned this a long time ago but didn't get any responses and then I got distracted. So this time I added a ticket and patch and everything: 2580

Here's the text: It's even implemented, but not exported. Without this, there's apparently no way to iterate over a map from high to low, since foldl is also not exported.

Hi, foldl is available via the Foldable instance for Set,Map,IntMap. And if I'm not mistaken, a 'left fold' corresponds to 'iterate from low to high' (try foldlM failing on the first element). Anyway, while there is foldWithKey

...

toAscList = foldWithKey (\k v m -> (k,v) : m) []

_foldrWithKey_ seems to be missing for Map/IntMap. I don't know if there is a performance penalty using 'reverse . toAscList' (e.g. in monadic traversals which stop after a few elements), but I suppose you were talking about the API anyway. Finally, I'd like to see a view on the association list, something like

...

viewAssocs :: Map k v -> MapView (k,v) instance Foldable MapView

which would provide 'fold[lr]WithKey[M]' in a standard way. best regards, benedikt

Evan Laforge

10:56 p.m.

On Wed, Sep 10, 2008 at 11:06 AM, Benedikt Huber wrote:

...

Evan Laforge schrieb:

...
So, I mentioned this a long time ago but didn't get any responses and then I got distracted. So this time I added a ticket and patch and everything: 2580

Here's the text: It's even implemented, but not exported. Without this, there's apparently no way to iterate over a map from high to low, since foldl is also not exported.

Hi, foldl is available via the Foldable instance for Set,Map,IntMap. And if I'm not mistaken, a 'left fold' corresponds to 'iterate from low to high' (try foldlM failing on the first element).

Oh right, I'm getting them backwards, because lists are build from back to front, so you apply the (:) from high to low, to generate a list from low to high efficiently. Then you iterate over that list from low to high, so high to low *application* via fold is actually low to high iteration via map... if I'm not even more confused now than before. But anyway, you're totally right about Foldable: 'take 10 $ Foldable.foldl (flip (:)) [] bigmap' seems to be quite fast and independent of the size of bigmap.

...

I don't know if there is a performance penalty using 'reverse . toAscList' (e.g. in monadic traversals which stop after a few elements), but I suppose you were talking about the API anyway.

reverse has a large performance penalty since it has to generate an entire forward list and traverse the entire thing. Here's the cpu time output from first a head . toAscList, and then a head . reverse . toAscList: 3164 -> (0,0) 3164 -> (10000000,10000000) 5434 So since there's Foldable.foldl, I guess this isn't so pressing. I still argue that it's more straightforward to simply export toDescList (why implement it and then not export it?) rather than make people roll their own with Foldable.

Evan Laforge

11 Sep 11 Sep

12:39 a.m.

...

So since there's Foldable.foldl, I guess this isn't so pressing. I still argue that it's more straightforward to simply export toDescList (why implement it and then not export it?) rather than make people roll their own with Foldable.

Oh, except the key part, of course. So I guess we need toDescList after all. 'foldr' and 'foldl' are also defined in the module so I took the liberty of renaming them 'WithKey' and exporting foldlWithKey (foldrWithKey is already exported as plain foldWithKey). There's also a foldlStrict, but I don't want to get too tangled up with all these details when all I really want is toDescList.

Evan Laforge

22 Sep 22 Sep

2:47 p.m.

...

Anyway, is 2-3 weeks ok for discussion period? The library submission wiki doesn't say how long.

So it's been a little while and there hasn't been any objection. What's the next step? Is there any problem with applying the patch as it stands and will it be in 6.10? To re-recap, it exports toDescList, and foldlWithKey. I'm assuming its current level of strictness is ok since no one has said anything. As an aside, it's curious to me that so few people care about Data.Map. In my code, it's the #1 data structure, except for lists, which almost all generated and consumed incrementally and thus take up little space and have simple access patterns. Data.Map does all the heavy lifting. Other people don't use it?

Ian Lynagh

3:46 p.m.

Hi Evan, On Mon, Sep 22, 2008 at 11:47:49AM -0700, Evan Laforge wrote:

...

...
Anyway, is 2-3 weeks ok for discussion period? The library submission wiki doesn't say how long.

So it's been a little while and there hasn't been any objection. What's the next step?

Please see: http://www.haskell.org/haskellwiki/Library_submissions#At_the_end_of_the_dis... (and if the concensus was to apply the patch, then you can assign the ticket to igloo). Thanks Ian

Evan Laforge

5:47 p.m.

...

...
So it's been a little while and there hasn't been any objection. What's the next step?

Please see: http://www.haskell.org/haskellwiki/Library_submissions#At_the_end_of_the_dis... (and if the concensus was to apply the patch, then you can assign the ticket to igloo).

Ok. I'm not sure what the consensus was since no one said "looks good", but I'm going to assume it was to apply, since no one said "looks bad" either. I'll add Benedikt's comments to the ticket in case someone later wants to implement his suggestion (viewAssocs). Here's what I added to the ticket when assigning to igloo: So on further thought, it seemed asymmetrical to export foldWithKey and foldlWithKey, so I added foldrWithKey to the export list, keeping foldWithKey to not break existing code. I added a note to the haddock for foldWithKey encouraging the use of foldrWithKey. So we export: toDescList - new, but implementable with foldlWithKey foldlWithKey - new foldrWithKey - the same as foldWithKey, but explicitly the mirror of foldlWithKey There were no other comments. I'm specifically not certain about the laziness of the folds (i.e. will they lead to stack problems like List.foldl), but no one said there was a problem, so maybe it's fine. I'm also not sure if there was some important reason behind the reason the folds were exported, but no one said anything, so maybe it was just arbitrary. --- As another aside, it seems like it would be nice to fix up Map, Set, IntMap, and IntSet, to hopefully give them a consistent API and maybe reduce some of the rampant copy and paste reuse going on in there. Maybe this GSoC thing for tries is doing that...

Christian Maeder

23 Sep 23 Sep

6:47 a.m.

Hi Evan, sorry for replying so late. I believe, many people are interested in a good Map data structure but do not care much if your proposed patch is applied or not. (The patch does not harm, toDescList is trivial to obtain, and the order of folding does not seem to matter.) (I'm not sure if foldrWithKey should be preferred over foldWithKey.) I've looked into the source and the (giant 338K) patch. The essence is attached below (You've renamed the internal foldr and foldl to foldlWithKey resp. foldrWithKey, which looks ok to me) Actually, Data.Map, Data.IntMap, Data.Set and Data.IntSet do not have an active maintainer and maybe everybody waits for "GSoC thing for tries". Indeed, as you noted yourself "it would be nice to fix up Map, Set, IntMap, and IntSet". I think it is almost mandatory. So would you do this, too? "toDescList" makes sense for sets, too. On the other hand, I was against toAscList as it is identical to toList. That means I always assumed a bias towards "ascending operations".

...

From a maintainer point of view the module is messy. (Many warnings when compiling.) For example I do not understand why the first pragma is needed: {-# OPTIONS_GHC -fno-bang-patterns #-}

Furthermore "foldi" is also defined but not used (but I do not propose it to be foldWithKey). (Other functions are also not exported.) Data.Map contains foldStrict: foldlStrict f z xs = case xs of [] -> z (x:xx) -> let z' = f z x in seq z' (foldlStrict f z' xx) Is there a difference to Data.List.foldl'? #ifdef __GLASGOW_HASKELL__ foldl' f z xs = lgo z xs where lgo z [] = z lgo z (x:xs) = let z' = f z x in z' `seq` lgo z' xs In order to refactor these modules a big test-suite is needed in order to ensure correctness and no performance loss. (So maybe it is wise to never change a running system.) Maybe this explains the little feedback to this ticket, but I would like to encourge you, to improve things, anyway. Cheers Christian Evan Laforge wrote:

...

Ok. I'm not sure what the consensus was since no one said "looks good", but I'm going to assume it was to apply, since no one said "looks bad" either. I'll add Benedikt's comments to the ticket in case someone later wants to implement his suggestion (viewAssocs).

Here's what I added to the ticket when assigning to igloo:

So on further thought, it seemed asymmetrical to export foldWithKey and foldlWithKey, so I added foldrWithKey to the export list, keeping foldWithKey to not break existing code. I added a note to the haddock for foldWithKey encouraging the use of foldrWithKey.

So we export: toDescList - new, but implementable with foldlWithKey foldlWithKey - new foldrWithKey - the same as foldWithKey, but explicitly the mirror of foldlWithKey

There were no other comments. I'm specifically not certain about the laziness of the folds (i.e. will they lead to stack problems like List.foldl), but no one said there was a problem, so maybe it's fine. I'm also not sure if there was some important reason behind the reason the folds were exported, but no one said anything, so maybe it was just arbitrary.

---

As another aside, it seems like it would be nice to fix up Map, Set, IntMap, and IntSet, to hopefully give them a consistent API and maybe reduce some of the rampant copy and paste reuse going on in there. Maybe this GSoC thing for tries is doing that...

hunk ./Data/Map.hs 106 + , foldrWithKey + , foldlWithKey hunk ./Data/Map.hs 123 + , toDescList hunk ./Data/Map.hs 176 -import Prelude hiding (lookup,map,filter,foldr,foldl,null) +import Prelude hiding (lookup,map,filter,null) hunk ./Data/Map.hs 1431 +-- +-- This is identical to 'foldrWithKey', and you should use that one inste ad of +-- this one. This name is kept for backward compatibility. hunk ./Data/Map.hs 1437 - = foldr f z t + = foldrWithKey f z t hunk ./Data/Map.hs 1448 --- | /O(n)/. Post-order fold. -foldr :: (k -> a -> b -> b) -> b -> Map k a -> b -foldr _ z Tip = z -foldr f z (Bin _ kx x l r) = foldr f (f kx x (foldr f z r)) l +-- | /O(n)/. Post-order fold. The function will be applied from the lowe st +-- value to the highest. +foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b +foldrWithKey _ z Tip = z +foldrWithKey f z (Bin _ kx x l r) = + foldrWithKey f (f kx x (foldrWithKey f z r)) l hunk ./Data/Map.hs 1455 -{- -XXX unused code hunk ./Data/Map.hs 1456 --- | /O(n)/. Pre-order fold. -foldl :: (b -> k -> a -> b) -> b -> Map k a -> b -foldl _ z Tip = z -foldl f z (Bin _ kx x l r) = foldl f (f (foldl f z l) kx x) r --} +-- | /O(n)/. Pre-order fold. The function will be applied from the highe st +-- value to the lowest. +foldlWithKey :: (b -> k -> a -> b) -> b -> Map k a -> b +foldlWithKey _ z Tip = z +foldlWithKey f z (Bin _ kx x l r) = + foldlWithKey f (f (foldlWithKey f z l) kx x) r hunk ./Data/Map.hs 1554 -toAscList t = foldr (\k x xs -> (k,x):xs) [] t +toAscList t = foldrWithKey (\k x xs -> (k,x):xs) [] t hunk ./Data/Map.hs 1556 -{- -XXX unused code - --- | /O(n)/. +-- | /O(n)/. Convert to a descending list. hunk ./Data/Map.hs 1558 -toDescList t = foldl (\xs k x -> (k,x):xs) [] t --} +toDescList t = foldlWithKey (\xs k x -> (k,x):xs) [] t

Evan Laforge

12:09 p.m.

...

sorry for replying so late. I believe, many people are interested in a good Map data structure but do not care much if your proposed patch is applied or not. (The patch does not harm, toDescList is trivial to obtain, and the order of folding does not seem to matter.)

That's one of the things I was asking... how do you obtain toDescList without foldlWithKey? And for me, since since the order of the keys is important (say points in time), the order of the fold matters a great deal.

...

(I'm not sure if foldrWithKey should be preferred over foldWithKey.)

Me either. On one hand, it's more api clutter. Once you add it, it never goes away. On the other hand, foldWithKey vs. foldlWithKey is just confusing. But if there was some sort of consensus that default is low to high, then I wouldn't mind so much. The unfortunate presence of both toList and toAscList seems to indicate a lack of consensus though (I think including both is silly too).

...

Actually, Data.Map, Data.IntMap, Data.Set and Data.IntSet do not have an active maintainer and maybe everybody waits for "GSoC thing for tries".

Indeed, as you noted yourself "it would be nice to fix up Map, Set, IntMap, and IntSet". I think it is almost mandatory. So would you do this, too? "toDescList" makes sense for sets, too. On the other hand, I was against toAscList as it is identical to toList. That means I always assumed a bias towards "ascending operations".

I wouldn't mind doing some cleanup, but I'm assuming any backward-incompatible api changes are out of the question. It seems like there should be the maplike equivalent of the IArray interface, or something clever like that. I know there has been a lot of discussion on this topic, and possibly even implementation in Edison. And then some discussion for the trie thing that sounded like a generic typeclass interface. So I feel like I should stick to conservative changes, i.e. just add new functions. It's also galling that IntMap is hardcoded to 32bit ints and writing a 64 bit version would seem to require yet another copy and paste session. And it seems like theoretically patricia should work on doubles too. But I'm not sure how to address all this code sharing. I agree the changes should be made to the other maplike modules, and I even wrote a foldl and toDescList for IntMap, but I was trying to the patch scope small, since I only need Map.toDescList.

...

In order to refactor these modules a big test-suite is needed in order to ensure correctness and no performance loss. (So maybe it is wise to never change a running system.)

Yes, no tests (that I could see) is another reason to be conservative making changes. I suppose I could write up some tests, but I remember there was some controversy about whether tests should be included in the ghc libs. And I'd be sort of surprised if someone else hasn't already written some? It would also be nice to have some time, garbage, and sharing (i.e. if you update a value how much of the structure is shared?) graphs generated for each of the operations. This would help evaluate new map implementations as well as check for the ramifications to various changes.

...

Maybe this explains the little feedback to this ticket, but I would like to encourge you, to improve things, anyway.

Well thanks. It's nice to hear *something* :)

Chris Kuklewicz

24 Sep 24 Sep

5:06 a.m.

...

Me either. On one hand, it's more api clutter. Once you add it, it never goes away. On the other hand, foldWithKey vs. foldlWithKey is just confusing. But if there was some sort of consensus that default is low to high, then I wouldn't mind so much. The unfortunate presence of both toList and toAscList seems to indicate a lack of consensus though (I think including both is silly too).

I conjecture that the logic, if any exists, behind having the two names is so that the Data.Map API can be applied to several implementations. And in another implementation it may be most efficient or most lazy to return elements in unsorted order. So there is a "toList" which asks for the easiest conversion to a list, and a "toAscList" which asks for the sorted version. As for this proposal, I vote to have toDescList and foldlWithKey. This would likely simplify one of my uses of Data.Map. -- Chris

Christian Maeder

6:15 a.m.

Chris Kuklewicz wrote:

...

I conjecture that the logic, if any exists, behind having the two names is so that the Data.Map API can be applied to several implementations. And in another implementation it may be most efficient or most lazy to return elements in unsorted order. So there is a "toList" which asks for the easiest conversion to a list, and a "toAscList" which asks for the sorted version.

if "toList" returned "elements in unsorted order" it would break the abstraction: equal maps could return different list. So toList must either be toAscList or toDescList.

...

As for this proposal, I vote to have toDescList and foldlWithKey. This would likely simplify one of my uses of Data.Map.

+1 and foldrWithKey. Christian

Evan Laforge

11 Oct 11 Oct

11:38 p.m.

On Mon, Sep 8, 2008 at 3:46 PM, Evan Laforge wrote:

...

So, I mentioned this a long time ago but didn't get any responses and then I got distracted. So this time I added a ticket and patch and everything: 2580

Sorry to dredge this one up again, but this patch was apparently applied more than a year ago, and yet when I look at the latest version 0.2.0.1 of containers on hackage, uploaded on April 2009, the changes aren't in the haddock (searching for toDescList reveals nothing). I was hoping to be able to finally remove my local hack! Was the patch applied? What's going on? Will 6.12 include it?

Simon Marlow

24 Nov 24 Nov

6 a.m.

On 12/10/2009 04:38, Evan Laforge wrote:

...

On Mon, Sep 8, 2008 at 3:46 PM, Evan Laforge wrote:

...
So, I mentioned this a long time ago but didn't get any responses and then I got distracted. So this time I added a ticket and patch and everything: 2580

Sorry to dredge this one up again, but this patch was apparently applied more than a year ago, and yet when I look at the latest version 0.2.0.1 of containers on hackage, uploaded on April 2009, the changes aren't in the haddock (searching for toDescList reveals nothing). I was hoping to be able to finally remove my local hack!

Was the patch applied? What's going on? Will 6.12 include it?

Yes, 6.12.1 includes that patch. Cheers, Simon

Evan Laforge

25 Nov 25 Nov

1:33 a.m.

...

Yes, 6.12.1 includes that patch.

Excellent. It's small but it makes me happy :)

5771

Age (days ago)

6214

Last active (days ago)

List overview

Download

13 comments

6 participants

participants (6)

Benedikt Huber
Chris Kuklewicz
Christian Maeder
Evan Laforge
Ian Lynagh
Simon Marlow