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

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

Мне интересно, возвращаются ли эти memoised значения в какой-то момент времени?

Если это так, это означает, что memoized значения должны быть пересчитаны позже, и преимущества memoization не так выходят из IMHO.
Если нет, то хорошо, это умно для кэширования всего... но означает ли это, что программа - если она будет работать в течение достаточно длительного периода времени - будет всегда потребляют все больше и больше памяти?

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

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

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

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

EDIT: Хорошо, я понимаю свою ошибку из первых ответов: Чистая семантика подразумевает ссылочную прозрачность, которая, в свою очередь, не подразумевает автоматическую Memoization, а просто гарантирует, что с ней не будет никаких проблем.

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

Ответ 1

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

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

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

fib n = fibs !! n

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

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

Ответ 2

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

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

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

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

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

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