Re: [Haskell-cafe] Observations about foldM

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 wrote:

2009/8/19 Dan Doel :

...

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