haskell - Why recursive `let` make space effcient? -

i found statement while studying functional reactive programming, "plugging space leak arrow" hai liu , paul hudak ( page 5) :

suppose wish define function repeats argument indefinitely:      repeat x = x : repeat x  or, in lambdas:      repeat = λx → x : repeat x  requires o(n) space. can achieve o(1) space writing instead:      repeat = λx → let xs = x : xs                   in xs 

the difference here seems small hugely prompts space efficiency. why , how happens ? best guess i've made evaluate them hand:

    r = \x -> x: r x     r 3      -> 3: r 3      -> 3: 3: 3: ........     -> [3,3,3,......] 

as above, need create infinite new thunks these recursion. try evaluate second one:

    r = \x -> let xs = x:xs in xs     r 3      -> let xs = 3:xs in xs     -> xs, according definition above:      -> 3:xs, xs = 3:xs     -> 3:xs:xs, xs = 3:xs 

in second form xs appears , can shared between every places occurring, guess that's why can require o(1) spaces rather o(n). i'm not sure whether i'm right or not.

btw: keyword "shared" comes same paper's page 4:

the problem here standard call-by-need evaluation rules unable recognize function:

f = λdt → integralc (1 + dt) (f dt)  

is same as:

f = λdt → let x = integralc (1 + dt) x in x 

the former definition causes work repeated in recursive call f, whereas in latter case computation shared.

it's easiest understand pictures:

• the first version

  repeat x = x : repeat x 

  creates chain of (:) constructors ending in thunk replace more constructors demand them. thus, o(n) space.

  

• the second version

  repeat x = let xs = x : xs in xs 

  uses let "tie knot", creating single (:) constructor refers itself.