export toDescList from Data.Map

[Christian Maeder]

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