Каково время жизни запомненного значения в функциональном языке, таком как Haskell?

Question

В чистом функциональном языке с ленивой семантикой (такой как Haskell) результаты вычислений запоминаются так, что дальнейшие вычисления функции с теми же входными данными не пересчитывают значение, а получают его непосредственно из кэша запомненных значений.

Мне интересно, будут ли эти запомненные значения повторно использованы в какой-то момент времени?

1. Если это так, это означает, что запомненные значения должны быть пересчитаны позднее, и преимущества запоминания не так уж важны для ИМХО.
2. Если нет, тогда ладно, это разумно для кэширования всего ... но означает ли это, что программа - если она выполняется в течение достаточно длительного периода времени - будет всегда потреблять больше и больше памяти?

Представьте себе программу, выполняющую интенсивный численный анализ: например, для поиска корней списка из сотен тысяч математических функций с использованием алгоритма дихотомии.

Каждый раз, когда программа оценивает математическую функцию с конкретным действительным числом, результат запоминается. Но есть только очень малая вероятность что точно такой же реальный номер снова появится во время алгоритма, что приведет к утечке памяти (или, по крайней мере, очень плохому использованию).

Моя идея заключается в том, что, возможно, запомненные значения просто «ограничиваются» чем-то в программе (например, текущим продолжением, стеком вызовов и т. Д.), Но я не смог найти что-то практическое по этому вопросу.

Признаюсь, я не слишком подробно изучал реализацию компилятора Haskell (ленивый?), Но, пожалуйста, кто-нибудь может объяснить мне, как это работает на практике?

---

РЕДАКТИРОВАТЬ: Хорошо, я понимаю свою ошибку из первых нескольких ответов: Чистая семантика подразумевает ссылочную прозрачность, которая, в свою очередь, не подразумевает автоматическую мемоизацию, а просто гарантирует, что с ней не будет проблем.

Я думаю, что некоторые статьи в Интернете вводят в заблуждение по этому поводу, потому что с точки зрения начинающего кажется, что свойство ссылочной прозрачности настолько круто, потому что оно позволяет неявное запоминание.

Answer 1

Haskell не автоматически запоминает вызовы функций именно потому, что это быстро потребляет тонны памяти. Если вы делаете памятку самостоятельно, вы можете выбрать, в какой области функция запоминается. Например, предположим, у вас есть функция Фибоначчи, определенная так:

fib n = fibs !! n
    where fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Здесь памятка производится только в течение одного вызова fib, тогда как если вы оставите fibs на верхнем уровне

fib n = fibs !! n

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

затем запомненный список сохраняется до тех пор, пока сборщик мусора не сможет определить, что больше нет способов достичь fibs из любой части вашей программы.

Answer 2

Моя идея заключается в том, что, возможно, запомненные значения просто «ограничиваются» чем-то в программе (например, текущим продолжением, стеком вызовов и т. Д.), Но я не смог найти что-то практичное по этому вопросу.

Это правильно.В частности, когда вы видите что-то вроде:

fun x y = let
    a = .....
    b = ....
    c = ....
in ....

или эквивалентного условия where, значения a, b и c могут не быть вычислены до фактического использования (или они могут быть вычислены сразу, потому что анализатор строгости можетдоказать, что значения будут оценены позже в любом случае).Но когда эти значения зависят от текущих параметров функции (здесь x и y), среда выполнения, скорее всего, не будет помнить каждую комбинацию x и y и результирующих a, b и c.

Обратите также внимание, что вна чистом языке, также можно вообще не запоминать значения - это практично, поскольку память дешевле, чем процессорное время.

Итак, ответ на ваш вопрос: не существует такой вещи, как время жизнипосреднические результаты в Haskell.Все, что можно сказать, это то, что оцененное значение будет там, когда это необходимо.