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