[Haskell-cafe] Observations about foldM

[Eugene Kirpichov]

You're right. My bad, indeed.

2009/8/19 Daniel Fischer <daniel.is.fischer at web.de>:
> 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
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>



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