[Haskell-cafe] Safer common subexpression elimination

[Joachim Breitner]

Hello Henning,


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

Right, sorry for the confusion by the wrong type.

Greetings,
Joachim
-- 
Joachim Breitner
  e-Mail: mail at joachim-breitner.de
  Homepage: http://www.joachim-breitner.de
  ICQ#: 74513189
  Jabber-ID: nomeata at joachim-breitner.de
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: This is a digitally signed message part
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20101204/0bf00762/attachment.pgp>