[Haskell-beginners] Where/Let clauses and subexpression repetition/memoization

[Brent Yorgey]

On Fri, Aug 19, 2011 at 09:43:13AM -0700, Tom Murphy wrote:
> On Fri, Aug 19, 2011 at 2:52 AM, Daniel Fischer <
> daniel.is.fischer at googlemail.com> wrote:
> 
> > [...] In most cases, you'll get recomputation,
> > but GHC does a bit of CSE, so in some cases it will compute only once and
> > share the result (which may be a bad thing - that's a further reason for
> > not doing too much CSE, sometimes sharing has catastrophic results).
> >
> >
> This is a beginner's list, so I'll ask: what catastrophic result could it
> have, if it's computing pure functions?

It cannot change the meaning of a program.  But it can drastically
change the memory usage.  For example, consider

  (length [1..1000000], sum [1..1000000])

vs.

  let x = [1..1000000] in (length x, sum x)

The first expression needs only a constant amount of memory, since
each list can be incrementally generated and garbage collected  while
accumulating the length and sum.  In the second program, however, x
cannot be garbage collected while length is being computed, since x is
still being referred to by sum.  So at the point just after evaluating
length and before starting in on evaluation of sum, the entire
million-element list is in memory.

-Brent