<div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">18.09.2012, 16:32, "Jan Stolarek" <<a href="mailto:jan.stolarek@p.lodz.pl">jan.stolarek@p.lodz.pl</a>>:<br>
<div class="HOEnZb"><div class="h5">> Hi list,<br>
><br>
> I have yet another question about folds. Reading here and there I encountered statements that<br>
> foldr is more important than foldl, e.g. in this post on the list:<br>
> <a href="http://www.haskell.org/pipermail/haskell-cafe/2012-May/101338.html" target="_blank">http://www.haskell.org/pipermail/haskell-cafe/2012-May/101338.html</a><span onmouseout="cancel = false; window.setTimeout(WRCHideContent, 1000); clearTimeout(showTimer);" onmouseover=" var self = this; showTimer = window.setTimeout(function(){WRCShowContent({'rating':{'value':99,'weight':14},'flags':{},'single':true,'ttl':7200,'expireTime':'20120918013022'}, self.className)},600);" class="wrc11" style="padding-right:16px;width:16px;height:16px"></span><br>
> I want to know are such statements correct and, if so, why? I am aware that foldl' can in some<br>
> circumstances operate in constant space, while foldr can operate on infinite lists if the folding<br>
> function is lazy in the second parameter. Is there more to this subject?<br></div></div></blockquote></div><br>Basically the difference is that foldr is really the natural catamorphism for the list type, that is for a type like :<br>
<br>data MyType = Zero | One A | Two B C | Recurse MyType<br><br>the natural catamorphism is a function that takes four arguments by which it will replace the four constructor so as to deconstruct a value of MyType :<br><br>
myTypeCata :: r -> (A -> r) -> (B -> C -> r) -> (r -> r) -> (MyType -> r)<br>myTypeCata z o t re Zero = z<br>myTypeCata z o t re (One a) = o a<br>myTypeCata z o t re (Two b c) = t b c<br>myTypeCata z o t re (Recurse myType) = re (myTypeCata z o t re myType)<br>
<br>So foldr is the natural catamorphism for the list type and foldl is not.<br><br>-- <br>Jedaï<br>