Когда в GHC Haskell происходит автоматическое запоминание?
Я не могу понять, почему m1 запомнился, а m2 нет в следующем:
m1 = ((filter odd [1..]) !!)
m2 n = ((filter odd [1..]) !! n)
m1 10000000 занимает около 1,5 секунд при первом вызове, и часть этого при последующих вызовах (предположительно, он кэширует список), тогда как m2 10000000 всегда занимает одинаковое количество времени (перестройка списка при каждом вызове). Есть идеи, что происходит? Есть ли какие-то практические правила относительно того, когда и когда GHC запомнит функцию? Благодарю.
4 ответа
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,
m1 вычисляется только один раз, потому что это постоянная аппликативная форма, в то время как m2 не является CAF, и поэтому вычисляется для каждой оценки.
Смотрите вики GHC на CAF: http://www.haskell.org/haskellwiki/Constant_applicative_form
Существует принципиальное различие между двумя формами: ограничение мономорфизма применяется к m1, но не к m2, потому что m2 явно дали аргументы. Итак, тип m2 общий, а тип m1 специфический. Типы, которым они назначены:
m1 :: Int -> Integer
m2 :: (Integral a) => Int -> a
Большинство компиляторов и интерпретаторов Haskell (все, что я знаю на самом деле) не запоминают полиморфные структуры, поэтому внутренний список m2 воссоздается каждый раз, когда он вызывается, а m1 - нет.
Я не уверен, потому что я сам новичок в 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-й элемент раньше.
Таким образом, если вы можете написать свою функцию так, чтобы она не принимала никаких параметров, вы, вероятно, захотите это.;)