Я нашел это выражение при изучении функционального реактивного программирования, от "Закрепление космического утечка со стрелкой" Хай Лю и Поля Худака (страница 5):
Suppose we wish to define a function that repeats its argument indefinitely: repeat x = x : repeat x or, in lambdas: repeat = λx → x : repeat x This requires O(n) space. But we can achieve O(1) space by writing instead: repeat = λx → let xs = x : xs in xs
Разница здесь кажется небольшой, но она чрезвычайно подсказывает эффективность пространства. Почему и как это происходит? Лучшее предположение, которое я сделал, это оценить их вручную:
r = \x -> x: r x
r 3
-> 3: r 3
-> 3: 3: 3: ........
-> [3,3,3,......]
Как и выше, нам нужно будет создать бесконечные новые thunks для этой рекурсии. Затем я пытаюсь оценить второй:
r = \x -> let xs = x:xs in xs
r 3
-> let xs = 3:xs in xs
-> xs, according to the definition above:
-> 3:xs, where xs = 3:xs
-> 3:xs:xs, where xs = 3:xs
Во второй форме появляется xs
и может делиться между всеми местами, которые он встречает, поэтому я предполагаю, что мы можем использовать только пробелы O(1)
, а не O(n)
. Но я не уверен, прав я или нет.
BTW: ключевое слово "shared" происходит из той же страницы 4:
Проблема заключается в том, что стандартные правила оценки по требованию не могут распознать, что функция:
f = λdt → integralC (1 + dt) (f dt)
совпадает с:
f = λdt → let x = integralC (1 + dt) x in x
Предыдущее определение заставляет работу повторяться в рекурсивном вызове к f, тогда как в последнем случае вычисление является общим.