Why recursive `let` make space effcient?

Solution 1:

It's easiest to understand with pictures:

• The first version

  repeat x = x : repeat x
  

  creates a chain of (:) constructors ending in a thunk which will replace itself with more constructors as you demand them. Thus, O(n) space.

  

• The second version

  repeat x = let xs = x : xs in xs
  

  uses let to "tie the knot", creating a single (:) constructor which refers to itself.

  

Solution 2:

Put simply, variables are shared, but function applications are not. In

repeat x = x : repeat x

it is a coincidence (from the language's perspective) that the (co)recursive call to repeat is with the same argument. So, without additional optimization (which is called static argument transformation), the function will be called again and again.

But when you write

repeat x = let xs = x : xs in xs

there are no recursive function calls. You take an x, and construct a cyclic value xs using it. All sharing is explicit.

If you want to understand it more formally, you need to familiarize yourself with the semantics of lazy evaluation, such as A Natural Semantics for Lazy Evaluation.

Solution 3:

Your intuition about xs being shared is correct. To restate the author's example in terms of repeat, instead of integral, when you write:

repeat x = x : repeat x

the language does not recognize that the repeat x on the right is the same as the value produced by the expression x : repeat x. Whereas if you write

repeat x = let xs = x : xs in xs

you're explicitly creating a structure that when evaluated looks like this:

{hd: x, tl:|}
^          |
 \________/