On Wed, Jun 15, 2011 at 5:15 AM, Milan Straka <span dir="ltr">&lt;<a href="mailto:fox@ucw.cz">fox@ucw.cz</a>&gt;</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;">
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>
There are several issues I am thinking about:<br>
<br>
a) we could left and right folds. For the Set and IntSet it is simple --<br>
   we can add foldr and foldl, and deprecated fold with the message &#39;use<br>
   foldr instead&#39;.<br>
<br>
   For the Map and IntMap it is not so simple -- should we add both<br>
   foldr, foldl, foldlWithKey and foldrWithKey?<br>
<br>
b) we could use the Foldable instances more. We can implement foldr and<br>
   foldl efficiently and let the users to use those instead of providing<br>
   eg Set.foldr, Set.foldl.<br>
<br>
   This does not cover the *WithKey variant, as the Foldable instances<br>
   over Map and IntMap does not utilize the key.<br></blockquote><div><br></div><div>In the keys package I have a notion of FoldableWithKey class that covers this use case, defined over a large number of data types, but it can&#39;t be used by containers as it requires a type family to talk about the container key, and it would be nice to have raw material to link it to. ;) There is also traverseWithKey.</div>
<div>  </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
c) strict folds. If we add also strict folds, we would have a total of<br>
   _four_ folds in Set and IntSet and __eight__ folds in Map and IntMap.<br>
<br>
   The Foldable module exports foldl&#39; and foldr&#39;, 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>
Personally I would add foldr, foldl, foldlWithKey, foldrWithKey and<br>
specialised foldr, foldl implementations in the Foldable classes.<br>
I am not sure about the strict folds -- I used an equivalent of the<br>
foldr&#39; from the Foldable module in GHC and it was reasonable fast.<br>
<br>
Any oppinions?<br>
<br>
Cheers,<br>
Milan<br>
<br>
_______________________________________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org">Libraries@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/libraries" target="_blank">http://www.haskell.org/mailman/listinfo/libraries</a><br>
</blockquote></div><br>