[Haskell-cafe] Observations about foldM

[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 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>



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