On Wed, Jun 15, 2011 at 8:43 AM, Duncan Coutts <span dir="ltr"><<a href="mailto:duncan.coutts@googlemail.com">duncan.coutts@googlemail.com</a>></span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div class="im">On Wed, 2011-06-15 at 11:15 +0200, Milan Straka wrote:<br>
> Hi all,<br>
><br>
> currently we have the following folds in the containers package:<br>
> Map: fold, foldWithKey, foldrWithKey, foldlWithKey<br>
> Set: fold<br>
> IntMap; fold, foldWithKey<br>
> IntSet: fold<br>
><br>
> If the direction (right, left) is not specified, the fold is the right<br>
> fold. So currently we have no left folds (except for the Map) and also<br>
> Map and IntMap are not consistent.<br>
<br>
</div>My recommendation is that we add all four folds:<br>
<br>
foldr, foldl'<br>
foldl, foldr'<br>
<br>
Don't get confused with thinking about the "direction". Direction is an<br>
implementation issue (albeit an important one). As you know, the 'l' and<br>
'r' in foldl and foldr are not direction but the left or right<br>
bracketing of the operations.<br>
<br>
left bracketing: ((0 + x_0) + x_1) + x_2<br>
right bracketing: x_0 + (x_1 + (x_2 + 0))<br>
<br>
Then the strictness is whether we reduce to WHNF before applying the<br>
operator.<br>
<br>
So I think those are the appropriate function names and abstract<br>
definitions, because they correspond to what we're all used to with<br>
lists. The implicit order of the order of the set/map keys, low to high.<br>
<br>
Now, when it comes to implementation the direction is important. The<br>
foldr and foldl' functions are best implemented as forwards/ascending<br>
traversals while foldl and foldr' are best implemented as<br>
backwards/descending traversals.<br>
<br>
In particular note that we can write things like:<br>
<br>
biggest = foldl (\y x -> x) undefined<br>
<br>
and evaluate it in O(log n) time. We get "early exit" behaviour.<br>
<br>
So by having all four traversals we cover the use cases where people<br>
want folds that start "from the back" (thinking about it operationally).<br>
<div class="im"><br>
> The Foldable module exports foldl' and foldr', which use foldr, foldl<br>
> respectively, but needs some intermediate memory (it creates a thunk<br>
> for every node of the structure). Apart from that, this does not<br>
> cover the *WithKey variants as in b).<br>
<br>
</div>This is unfortunate. For data structures with equal access to all<br>
elements (arrays, map/set etc) we can implement foldl' and foldr'<br>
directly and more efficiently.</blockquote><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
Perhaps you need the withKey variety too. Do provide a Foldable<br>
instance, and perhaps later we can lobby for foldl' and foldr' to be<br>
made members of the Foldable class rather than fixed definitions in<br>
terms of foldl and foldr (bytestring, vector and text could benefit from<br>
this too).</blockquote><div><br></div><div> </div><div><div>I vaguely recall a discussion about adding them to the Foldable class with the current definitions as defaults, but I don't think an actual libraries@ submission was ever made. I would definitely support this motion.</div>
</div><div><br></div><div>-Edward</div></div>