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

Question

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

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

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

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

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

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

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

РЕДАКТИРОВАТЬ:! используется для доступа к массиву, так что fA! 5 означает fA [5] в синтаксисе C ++. Я понимаю, что Haskell (fA!) N будет таким же, как (fA! N) ... и для меня было бы более привычным написать "f n = fA! N" (без скобок). Во всяком случае, я получаю одинаковое поведение независимо от того, как заключить в скобки.

Answer 1

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

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

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

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

Компиляторы используют let привязки, чтобы указать совместное использование. Гарантия заключается в том, что в данной среде (набор локальных переменных, лямбда-тело, что-то в этом роде) правая сторона привязки 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

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

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

Answer 2

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

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

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

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

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

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

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

Answer 3

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