Am Sonntag, 26. Juni 2005 06:06 schrieb Scott Turner:
On 2005 June 25 Saturday 17:49, kynn@panix.com wrote:
Simplified: prodList xs = foldl (*) 1 xs
But my original at least made some provision for short circuiting the whole operation if the list contained a 0. As far as I can figure, fold, map, etc., are not suitable for any situation in which short-circuiting would be desirable (e.g. and, or, etc.). Am I wrong?
Actually, foldr is applicable to short-circuiting. foldr (&&) True works fine for detecting whether all elements of a list are True, and does not evaluate the list beyond the first occurrence of False. Similarly, if `m` is defined as a short-circuiting multiplication operator, i.e. m x y = if x==0 then 0 else x*y then foldr m 1 does not evaluate the list beyond the first occurrence of 0. Unfortunately, `m` does not work as well with foldr as &&. The function (foldr m 1) creates a stack containing one (*) operation for every list element to be multiplied, which can cause undesirable memory usage.
It's still possible to use fold and get short circuiting with good memory usage. upTo pred = foldr (\a -> \xs -> if pred a then [a] else a:xs) [] prodList = foldl' (*) 1 . upTo (== 0) It might be considered cheating, but AFAICT the test for ==0 needs to be separated from the multiplication proper.
Plain foldr m 1 does fine, in fact much better than foldl' (*) 1 . upTo (== 0), both in hugs and ghc, regarding speed and memory usage. Cheers, Daniel