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