Когда в GHC Haskell автоматическая автоматизация?

Ответ 1

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

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

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.

Ответ 2

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

См. вики GHC в CAFs: http://www.haskell.org/haskellwiki/Constant_applicative_form

Ответ 3

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

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

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

Ответ 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-й элемент раньше.

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