[Haskell-cafe] Observations about foldM
Daniel Fischer
daniel.is.fischer at web.de
Wed Aug 19 10:44:52 EDT 2009
Am Mittwoch 19 August 2009 16:32:57 schrieb Eugene Kirpichov:
> 2009/8/19 Dan Doel <dan.doel at 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 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
More information about the Haskell-Cafe
mailing list