export toDescList from Data.Map

[Evan Laforge]

On Wed, Sep 10, 2008 at 11:06 AM, Benedikt Huber <benjovi at gmx.net> 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.