Когда автоматическое запоминание происходит в GHC Haskell?

Question

Я не могу понять, почему m1 явно запоминается, а m2 отсутствует в следующем:

m1      = ((filter odd [1..]) !!)

m2 n    = ((filter odd [1..]) !! n)

m1 10000000 занимает около 1,5 секунд при первом вызове, и часть этого при последующих вызовах(предположительно, он кэширует список), тогда как m2 10000000 всегда занимает одинаковое количество времени (перестройка списка с каждым вызовом).Есть идеи, что происходит?Существуют ли какие-либо практические правила относительно того, когда и когда GHC запомнит функцию?Спасибо.

Answer 1

GHC не запоминает функции.

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

m1' = (!!) (filter odd [1..])              -- NB: See below!
m2' = \n -> (!!) (filter odd [1..]) n

(Примечание. В отчете на Haskell 98 фактически описывается левая секция оператора, такая как (a %), эквивалентная \b -> (%) a b, но GHC обнуляет ее до (%) a. Они технически отличаются, поскольку их можно отличить seq. Я думаю, что мог бы подать билет GHC Trac об этом.)

Учитывая это, вы можете видеть, что в m1' выражение filter odd [1..] не содержится ни в одном лямбда-выражении, поэтому оно будет вычисляться только один раз за запуск вашей программы, тогда как в m2', filter odd [1..] будет вычисляться каждый раз при вводе лямбда-выражения, т. е. при каждом вызове m2'. Это объясняет разницу во времени, которое вы видите.

---

На самом деле, некоторые версии GHC с определенными параметрами оптимизации будут иметь больше значений, чем указано в приведенном выше описании. Это может быть проблематично в некоторых ситуациях. Например, рассмотрим функцию

f = \x -> let y = [1..30000000] in foldl' (+) 0 (y ++ [x])

GHC может заметить, что y не зависит от x, и переписать функцию на

f = let y = [1..30000000] in \x -> foldl' (+) 0 (y ++ [x])

В этом случае новая версия намного менее эффективна, поскольку ей придется считывать около 1 ГБ из памяти, в которой хранится y, тогда как исходная версия будет работать в постоянном пространстве и помещаться в кэш процессора. Фактически, в GHC 6.12.1 функция f почти в два раза быстрее при компиляции без оптимизаций, чем при компиляции с -O2.

Answer 2

m1 рассчитывается только один раз, потому что это постоянная аппликативная форма, в то время как m2 не является CAF, поэтому рассчитывается для каждой оценки.

См. Вики GHC по CAF: http://www.haskell.org/haskellwiki/Constant_applicative_form

Answer 3

Существует принципиальное различие между этими двумя формами: ограничение мономорфизма применяется к m1, но не к m2, потому что m2 явно предоставили аргументы. Таким образом, тип m2 общий, а тип m1 специфический. Им присваиваются следующие типы:

m1 :: Int -> Integer
m2 :: (Integral a) => Int -> a

Большинство компиляторов и интерпретаторов Haskell (все, которых я знаю на самом деле) не запоминают полиморфные структуры, поэтому внутренний список m2 воссоздается каждый раз, когда он вызывается, а m1 - нет.

Answer 4

Я не уверен, потому что я сам новичок в Haskell, но похоже, что это потому, что вторая функция параметризована, а первая нет.Природа функции заключается в том, что ее результат зависит от входного значения, а в функциональной парадигме, в частности, зависит только от входного значения.Очевидно, что функция без параметров возвращает всегда одно и то же значение снова и снова, несмотря ни на что.

Очевидно, в компиляторе GHC есть оптимизирующий механизм, который использует этот факт для вычисления значения такой функции только один раз.для всей программы.Конечно, он делает это лениво, но, тем не менее, делает это.Я заметил это сам, когда написал следующую функцию:

primes = filter isPrime [2..]
    where isPrime n = null [factor | factor <- [2..n-1], factor `divides` n]
        where f `divides` n = (n `mod` f) == 0

Затем, чтобы проверить это, я вошел в GHCI и написал: primes !! 1000.Прошло несколько секунд, но наконец я получил ответ: 7927.Затем я позвонил primes !! 1001 и сразу получил ответ.Точно так же в одно мгновение я получил результат для take 1000 primes, потому что Haskell должен был вычислить весь список из тысячи элементов, чтобы вернуть 1001-й элемент раньше.

Таким образом, если вы можете написать свою функцию так, что она не принимает параметровВы, вероятно, хотите это.;)