Возникли проблемы с функцией в схеме

Question

Поэтому я пытаюсь понять этот кусок кода, и, посмотрев на него слишком долго, я решил спросить здесь, может ли кто-нибудь помочь мне понять, как и почему он работает

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

Затем функция вызывается по имени со значением:

(list-ref knock-knock 5)

Поэтому моя главная проблема в том, что я не вижу, где letrec закончится Другое дело, что мне не дают список, так что же это за 4-й элемент в списке, на который я должен ссылаться в строке 3?

Answer 1

Во-первых, примечание: это не нормальная схема, так как требует ленивой оценки.

При отложенной оценке значения вычисляются только тогда, когда они необходимы. Итак, для определения knock-knockмы можем просто сделать

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

мы генерируем пару, но нам не нужен второй элемент, поэтому мы отложим его оценку до следующего.

Когда мы действительно хотим оценить второй элемент, у нас уже будет knock-knock определены, поэтому мы можем ссылаться на него.

Следующий элемент вычисляется путем взятия предыдущего (i-1-st) элемент и умножает его на i, Так что это сгенерирует серию {n!}: 1,1,2,6,24,...

Простой перевод этого кода на (обычно ленивый) язык Haskell выглядит следующим образом:

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