Определение функции Haskell и кеширование

У меня вопрос о реализации кэширования (memoization) с использованием массивов в Haskell. Работает следующий шаблон:

f = (fA !)
  where fA = listArray...

Но это не так (скорость программы предполагает, что массив получает воссозданный каждый вызов или что-то еще):

f n = (fA ! n)
  where fA = listArray...

Определение fA вне предложения where (в "глобальной области видимости" ) также работает с любым шаблоном.

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

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

ИЗМЕНИТЬ:! используется для доступа к массиву, поэтому fA! 5 означает fA [5] в синтаксисе С++. Мое понимание Haskell заключается в том, что (fA!) N будет таким же, как (fA! N)... и для меня было бы более обычным писать "f n = fA! N" (без круглых скобок). Во всяком случае, я получаю такое же поведение независимо от того, как я заключу в скобки.

Ответ 1

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

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

Сначала перепишите два примера в виде чистых лямбда-выражений, расширив раздел:

f = let fA = listArray ... in \n -> fA ! n
f' = \n -> let fA = listArray ... in fA ! n

Компиляторы используют let binding для обозначения совместного использования. Гарантия заключается в том, что в заданной среде (набор локальных переменных, лямбда-тела, что-то вроде этого) правая сторона связывания let без параметров будет оцениваться не более одного раза. Среда fA в первой - это вся программа, поскольку она не находится ни под какой лямбдой, но среда последней меньше, поскольку она находится под лямбдой.

Это означает, что в последнем случае fA может оцениваться один раз для каждого другого n, тогда как в первом это запрещено.

Мы можем видеть, что этот шаблон действует даже при использовании нескольких аргументов:

g x y = (a ! y) where a = [ x ^ y' | y' <- [0..] ]
g' x = (\y -> a ! y) where a = [ x ^ y' | y' <- [0..] ]

Тогда в:

let k = g 2 in k 100 + k 100

Мы могли бы вычислить 2 ^ 100 более одного раза, но в:

let k = g' 2 in k 100 + k 100

Мы вычислим его только один раз.

Если вы выполняете работу с memoization, я рекомендую использовать данные-памятные компиляторы в Hackage, которая представляет собой библиотеку таблиц заметок разных форм, поэтому вам не нужно сворачивать свои собственные.

Ответ 2

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

Вероятно, вы заметите, что fA перемещается за пределы функции (в "глобальную область" ) в первом примере. На втором примере это, вероятно, нет (это означает, что он будет воссоздан при каждом вызове).

Одна из возможных причин, по которой он не перемещается за пределы функции, будет заключаться в том, что компилятор думает, что это зависит от значения n. В вашем рабочем примере для fA не существует n.

Но причина, по которой я думаю, что компилятор избегает перемещения fA снаружи на вашем втором примере, заключается в том, что он пытается избежать утечки пространства. Подумайте, что произойдет, если fA вместо вашего массива будет бесконечным списком (на котором вы использовали оператор !!). Представьте, что вы вызвали его один раз с большим числом (например, f 10000), а позже называли его только небольшими числами (f 2, f 3, f 12...). 10000 элементов из предыдущего вызова все еще находятся в памяти, теряя пространство. Поэтому, чтобы этого избежать, компилятор создает fA снова каждый раз, когда вы вызываете свою функцию.

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

Если вы хотите попытаться понять больше этого (что поможет прочитать вывод -v4), вы можете взглянуть на Spineless Tagless G -Machine (ссылка citeseer).

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

Ответ 3

Прохладный, спасибо за ваши ответы, которые очень помогли, и я обязательно проверю данные-памятные компиляторы в Hackage. Исходя из С++ - тяжелого фона, я изо всех сил пытался понять, что Haskell будет делать (в основном с точки зрения сложности) с помощью данной программы, на которые, похоже, не участвуют учебные пособия.