On Wed, 14 May 2008, Paul Johnson wrote:
We've had a big debate over
mean xs = foldl' (+) 0 xs / fromIntegral (length xs)
For anyone who didn't follow it, the problem is that "mean" needs to traverse
its argument twice, so the entire list has to be held in memory. So if "xs =
[1..1000000000]" then "mean xs" uses all your memory, but "foldl' (+) 0 xs"
and "length xs" by themselves do not.
I also wondered how to solve that problem. It also occurs in
implementations of "wc", that is counting lines, words and characters of a
text in parallel.
The solution is for the programmer to rewrite "mean" to accumulate a pair
containing the running total and count together, then do the division. This
makes me wonder: could there be a compiler optimisation rule for this,
collapsing two iterations over a list into one. I've never tried writing GHC
rules, but something like:
f (foldl' g x) (foldl' h x) = (uncurry f) (foldl' (\i (gt,ht) -> (g i gt, h i
ht)))
The left hand sides of GHC rules must have a definite function as
top-level construct, whereas 'f' is a variable. You may define a function
which points the optimizer to the places where something shall be
replaced. Say
fuseFold :: (a -> b -> c) -> a -> b -> c
fuseFold f x y = f x y
{-# RULES
forall f g h x y.
fuseFold f (foldl' g x) (foldl' h x) = ...
#-}
However, instead of writing library functions which use foldl', it might
be better to implement and export the accumulating functions separately.
They can be used with 'foldl's of arbitrary data structures and they can
be fused explicitly without GHC rules. However, I suspect you cannot
rewrite say (length (words str)) or (length (lines str)) in that manner in
an elegant way.
The first problem that occurs to me is the number of permutations of fold and
map functions.
foldl' could be merged with 'map' to a foldl', however the existing fusion
frameworks use different primitives, like foldr/build.
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
