Re: [Haskell-cafe] Observations about foldM

You're right. My bad, indeed. 2009/8/19 Daniel Fischer :

Am Mittwoch 19 August 2009 16:32:57 schrieb Eugene Kirpichov:

...

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 is true: foldr: A1*(A2*(... *AN*E)) foldl: (...((E*A1)*A2)*...*AN)

Commutativity doesn't help, consider

data Foo = Z | A | B

(~) :: Foo -> Foo -> Foo Z ~ x = x x ~ Z = x B ~ B = A _ ~ _ = B

(~) is commutative, but not associative, Z is a unit for (~).

foldr (~) Z [A,A,B] = B foldl (~) Z [A,A,B] = A

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Eugene Kirpichov Web IR developer, market.yandex.ru