export toDescList from Data.Map

Evan Laforge qdunkan at gmail.com
Wed Sep 10 22:56:03 EDT 2008


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.


More information about the Libraries mailing list