GHC Haskell에서 자동 메모는 언제 이루어 집니까?

GHC Haskell에서 자동 메모는 언제 이루어 집니까?

---

m2가 다음에 없는데 m1이 분명히 메모 된 이유를 알 수 없습니다.

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

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

m1 10000000은 첫 번째 호출에서 약 1.5 초가 걸리고 후속 호출에서 그 일부 (아마도 목록을 캐시 함)에 걸리는 반면 m2 10000000은 항상 같은 시간 (각 호출로 목록을 다시 작성)이 걸립니다. 무슨 일인지 아십니까? GHC가 함수를 메모할지 여부와시기에 대한 경험 규칙이 있습니까? 감사.

---

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])

이 경우 새 버전은 y저장된 메모리에서 약 1GB를 읽어야 하므로 원래 버전은 일정한 공간에서 실행되고 프로세서 캐시에 맞기 때문에 훨씬 덜 효율적 입니다. 실제로 GHC 6.12.1에서이 함수 f는 최적화 없이 컴파일 할 때 -O2.

---

m1은 상수 적용 양식이기 때문에 한 번만 계산되고 m2는 CAF가 아니므로 각 평가에 대해 계산됩니다.

CAF에 대한 GHC wiki를 참조하십시오 : http://www.haskell.org/haskellwiki/Constant_applicative_form

---

두 형식 사이에는 결정적인 차이가 있습니다. m2가 명시 적으로 인수를 제공했기 때문에 단 형성 제한은 m1에는 적용되지만 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 primesHaskell은 이전에 1001 번째 요소를 반환하기 위해 전체 1,000 개 요소 목록을 계산해야했기 때문입니다.

따라서 매개 변수를 사용하지 않도록 함수를 작성할 수 있다면 아마도 그것을 원할 것입니다. ;)

참고 URL : https://stackoverflow.com/questions/3951012/when-is-memoization-automatic-in-ghc-haskell