Как определить, будет ли Haskell кэшировать результат или пересчитать его?

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

  • Почему это происходит? Это функция GHCI или что?
  • Могу ли я полагаться на это (то есть: могу ли я детерминистически знать, будет ли кэшировано значение функции)?
  • Могу ли я принудительно отключить эту функцию для некоторых вызовов функций?

В соответствии с комментариями, вот пример, который я нашел в Интернете:

isPrime a = isPrimeHelper a primes
isPrimeHelper a (p:ps)
    | p*p > a = True
    | a `mod` p == 0 = False
    | otherwise = isPrimeHelper a ps
primes = 2 : filter isPrime [3,5..]

Я ожидал, прежде чем запускать его, довольно медленно, так как он продолжает получать доступ к элементам primes без явного кэширования их (таким образом, если эти значения не кэшированы где-то, их нужно будет перечитать много раз). Но я был неправ.

Если я устанавливаю +s в GHCI (для печати статистики времени/памяти после каждой оценки) и дважды оцениваю выражение primes!!10000, это то, что я получаю:

*Main> :set +s
*Main> primes!!10000
104743
(2.10 secs, 169800904 bytes)
*Main> primes!!10000
104743
(0.00 secs, 0 bytes)

Это означает, что по крайней мере primes !! 10000 (или лучше: весь список primes, так как также primes!!9999 не займет времени) должен быть кэширован.

Ответы

Ответ 1

primes, в вашем коде не является функцией, а константой, в haskellspeak, известной как CAF. Если бы он принял параметр (скажем, ()), вы бы получили две разные версии одного и того же списка, если вы вызываете его дважды, но поскольку это CAF, вы получаете тот же самый список обратно оба раза;

Как определение верхнего уровня ghci, primes никогда не становится недоступным, поэтому глава списка, на который он указывает (и, следовательно, его хвост/остальная часть вычисления), никогда не собирает мусор. Добавление параметра предотвращает сохранение этой ссылки, тогда список будет собираться мусором, поскольку (!!) выполняет итерацию вниз, чтобы найти правильный элемент, а второй вызов (!!) заставит повторение всего вычисления вместо того, вычисленный список.

Обратите внимание, что в скомпилированных программах отсутствует область верхнего уровня, например, в ghci, и вещи получают сбор мусора, когда последняя ссылка на них ушла, скорее всего, до выхода всей программы CAF или нет, что означает, что ваш первый вызов займет много времени, второе - нет, и после этого "будущее вашей программы" больше не ссылается на CAF, память, которую занимает CAF, перерабатывается.

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

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