Оптимизация вызовов функций в Haskell

Не уверен, что именно для Google для этого вопроса, поэтому я отправлю его непосредственно в SO:

  • Переменные в Haskell неизменяемы.
  • Чистые функции должны приводить к одинаковым значениям для одних и тех же аргументов

Из этих двух точек можно сделать вывод, что если вы дважды вызываете somePureFunc somevar1 somevar2 в свой код, имеет смысл вычислить значение во время первого вызова. Результирующее значение может быть сохранено в виде гигантской хеш-таблицы (или что-то в этом роде) и посмотрело вверх во время последующих вызовов функции. У меня есть два вопроса:

  • Действительно ли GHC делает такую ​​оптимизацию?
  • Если это так, то каково поведение в случае, когда на самом деле дешевле повторять вычисление, чем искать результаты?

Спасибо.

Ответы

Ответ 1

GHC не выполняет автоматический memoization. См. FAQ по GHC на Общее ограничение подвыражения (не совсем то же самое, но я предполагаю, что рассуждение одинаков) и ответ на этот вопрос.

Если вы хотите сделать memoization самостоятельно, посмотрите на Data.MemoCombinators.

Еще один способ взглянуть на memoization - использовать лень, чтобы воспользоваться мемуаризацией. Например, вы можете определить список в терминах самого себя. Нижеприведенное определение представляет собой бесконечный список всех чисел Фибоначчи (взятых из Haskell Wiki)

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

Поскольку список реализуется лениво, он аналогичен предварительному (memoized) предыдущим значениям. например fibs !! 10 создаст первые десять элементов, так что fibs 11 будет намного быстрее.

Ответ 2

Сохранение каждого результата вызова функции (см. hash consing) является допустимым, но может представлять собой гигантскую утечку пространства и, в общем, также замедляет вашу программу. Это часто стоит больше, чтобы проверить, есть ли у вас что-то в таблице, чем вычислять его.