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

Question

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

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

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

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

Спасибо.

Answer 1

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

Если вы хотите сделать памятку самостоятельно, взгляните на Data.MemoCombinators .

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

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

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

Answer 2

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