2009/8/19 Dan Doel <dan.d...@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@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
