Having trouble with a function in Scheme

Question

so i am trying to understand this piece of code, and after staring at it for far too long i decided to ask here if anyone could help me understand how and why it works

(define knock-knock
 (letrec ([dig (lambda (i)
                 (cons (* i (list-ref knock-knock (- i 1)))
                       (dig (+ i 1))))])
   (cons 1 (dig 1))))

the function is then called by name with the value:

(list-ref knock-knock 5)

So my main problem is that i can not see where the letrec would end. the other thing is that i am not given a list, so what is the 4th element in the list that i am supposed to reference in line 3?

Answer 1

First, a note: this is not normal Scheme, as it requires lazy evaluation.

In lazy evaluation, values are only computed when they are needed. So, for defining knock-knock, we can just do

(cons 1 <thunk: (dig 1)>)

i.e., we generate a pair, but we don't need the second element, so we defer its evaluation until later.

When we actually want to evaluate the second element, we will already have knock-knock defined, so we can reference it.

The next element is computed by taking the previous (i-1-st) element, and multiplies it by i. So this will generate the series {n!}: 1,1,2,6,24,...

A straightforward translation of this code to the (normally lazy) Haskell language goes like this:

knock :: [Int]
knock = 1 : dig 1
    where dig i = (i * knock !! (i-1)) : dig (i+1)