export toDescList from Data.Map

Evan Laforge qdunkan at gmail.com
Tue Sep 23 12:09:44 EDT 2008

> 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

> 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* :)

More information about the Libraries mailing list