[Haskell-cafe] Observations about foldM

[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.

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