<div>It is associativity that is required, not commutativity (in addition to the fact that the list is finite).</div>
<div> </div>
<div>This is why Data.Foldable provides operations for monoids over containers. Monoids just provide you with associativity and a unit, which lets you reparenthesize the fold however you want.</div>
<div> </div>
<div>See the monoids library or my slides from hac-phi for lots of (ab)uses of a monoid's associativity.</div>
<div> </div>
<div><a href="http://comonad.com/reader/2009/hac-phi-slides/">http://comonad.com/reader/2009/hac-phi-slides/</a></div>
<div> </div>
<div>-Edward Kmett<br><br></div>
<div class="gmail_quote">On Wed, Aug 19, 2009 at 10:32 AM, Eugene Kirpichov <span dir="ltr"><<a href="mailto:ekirpichov@gmail.com">ekirpichov@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid">2009/8/19 Dan Doel <<a href="mailto:dan.doel@gmail.com">dan.doel@gmail.com</a>>:<br>
<div class="im">> On Wednesday 19 August 2009 12:14:24 am Jason McCarty wrote:<br>>> Interestingly, foldM can also be written as a left fold. To see this, note<br>>> that it is a theorem that foldr f z xs = foldl f z xs as long as f is<br>
>> associative and z is a unit for f.<br>><br><br></div>This is not true: f has to be commutative, not associative.<br><br>Consider matrix multiplication.<br>
<div class="im"><br>> It must also be the case that xs is finite in length, because if it is<br>> infinite, then 'foldl f z xs' is bottom, while 'foldr f z xs' needn't be. This<br>> difference holds over into foldM implemented with each, where you can write<br>
> something like:<br>><br>> foldM (\f e -> if even e then Left (show e) else Right f) "no evens" [1..]<br>><br>> and get an answer of 'Left "2"' with a foldr implementation, but bottom with a<br>
> foldl implementation.<br>><br>> This potentially translates into its own performance concerns, because in such<br>> monads, the computation can short-circuit upon finding a 'throw' when using<br>> the foldr implementation, but with the foldl implementation, you have to do at<br>
> least a little shuffling of thunks for the entire list.<br>><br>> -- Dan<br>> _______________________________________________<br>> Haskell-Cafe mailing list<br>> <a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
> <a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>><br><br><br><br></div><font color="#888888">--<br>Eugene Kirpichov<br>Web IR developer, <a href="http://market.yandex.ru/" target="_blank">market.yandex.ru</a><br>
</font>
<div>
<div></div>
<div class="h5">_______________________________________________<br>Haskell-Cafe mailing list<br><a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br><a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
</div></div></blockquote></div><br>