[Haskell-cafe] Safer common subexpression elimination

Henning Thielemann schlepptop at henning-thielemann.de
Sat Dec 4 22:01:46 CET 2010

Joachim Breitner schrieb:

> Am Samstag, den 04.12.2010, 12:41 +0100 schrieb Henning Thielemann:
>> Joachim Breitner schrieb:
>>> 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)
>> ?
> Thanks for noting. The type annotation is wrong. In your case (which I
> had first), ns is shared and thus would not allow for constant-space
> calculation of sum and length and would fail to demonstrate my point.

I see. It may be that GHC actually eliminates common subexpression of
primitive types. Its Core output will tell you.

Nonetheless, maybe it is more sensible for a compiler not to answer the
question whether a common subexpression should be shared or not, but it
may try to evaluate the depending expressions in a way such that the
shared data structure can be garbage collected as computation goes on.

More information about the Haskell-Cafe mailing list