It is associativity that is required, not commutativity (in addition to the fact that the list is finite).
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. See the monoids library or my slides from hac-phi for lots of (ab)uses of a monoid's associativity. http://comonad.com/reader/2009/hac-phi-slides/ -Edward Kmett On Wed, Aug 19, 2009 at 10:32 AM, Eugene Kirpichov <ekirpic...@gmail.com>wrote: > 2009/8/19 Dan Doel <dan.d...@gmail.com>: > > On Wednesday 19 August 2009 12:14:24 am Jason McCarty wrote: > >> Interestingly, foldM can also be written as a left fold. To see this, > note > >> that it is a theorem that foldr f z xs = foldl f z xs as long as f is > >> associative and z is a unit for f. > > > > This is not true: f has to be commutative, not associative. > > Consider matrix multiplication. > > > It must also be the case that xs is finite in length, because if it is > > infinite, then 'foldl f z xs' is bottom, while 'foldr f z xs' needn't be. > This > > difference holds over into foldM implemented with each, where you can > write > > something like: > > > > foldM (\f e -> if even e then Left (show e) else Right f) "no evens" > [1..] > > > > and get an answer of 'Left "2"' with a foldr implementation, but bottom > with a > > foldl implementation. > > > > This potentially translates into its own performance concerns, because in > such > > monads, the computation can short-circuit upon finding a 'throw' when > using > > the foldr implementation, but with the foldl implementation, you have to > do at > > least a little shuffling of thunks for the entire list. > > > > -- Dan > > _______________________________________________ > > Haskell-Cafe mailing list > > Haskell-Cafe@haskell.org > > http://www.haskell.org/mailman/listinfo/haskell-cafe > > > > > > -- > Eugene Kirpichov > Web IR developer, market.yandex.ru > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
