Joachim Breitner schrieb: > Hi, > > although semantically it could, ghc does not do common subexpression > elimination (CSE), at least not in every case. The canonical example > where it would be bad is the function (with div to avoid numerical > casting): > >> avg :: [Int] -> Int >> avg n = (sum [0..n] `div` length [0..n]) > > The reason why [0..n] is not shared is because then it would be kept in > memory completely after the evaluation of sum, because length will still > need it, possibly overflowing the memory. In the non-shared form, > though, the garbage collector can clean up directly behind sum and > length, and the program runs in constant space. > > Note that the shared expression would be very large compared to the > thunks. > > Now consider the program: > >> avg' :: [Int] -> (Int, Int) >> avg' n = (sum [0..n] `div` length [0..n], length [0..n])
It think this is not typecorrect, since 'n' denotes a list and is used as upper bound in [0..n]. Should it be > avg' ns = (sum ns `div` length ns, length ns) ? > I’d say that CSE to >> avg n = (sum [0..n] `div` l, l) >> where l = length [0..n] > is safe, because the shared expression (an Int) is smaller than the > thunks and the compiler can tell. If this is meant to be > avg n = (sum ns `div` l, l) > where l = length ns according to my substitution above, then 'ns' still has to be shared and stored completely. I think the general problem is more complicated than common subexpression elimination, because lazy evaluation sometimes forces an inefficient order of computation. Other examples are > viewR xs = (init xs, last xs) and an elegant Haskell implementation of the Unix command 'wc' like > wc text = (length text, length (words text), length (lines text)) _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
