[haskell] 이 피보나치 함수는 어떻게 메모됩니까?

하스켈 평가 메커니즘은 별로 필요가 값이 필요할 때, 그것을 계산하고 다시 요구되는 경우에 준비가 유지된다. 일부 목록을 정의 xs=[0..]하고 나중에 100 번째 요소 인을 요청 xs!!99하면 목록의 100 번째 슬롯이 “살아남” 99상태가되어 현재 번호를 보유하고 다음 액세스를 준비합니다.

이것이 바로 “목록을 통과하는”트릭이 악용하는 것입니다. 정상적인 이중 재귀 피보나치 정의 fib n = fib (n-1) + fib (n-2)에서 함수 자체가 맨 위에서 두 번 호출되어 지수 폭발을 일으 킵니다. 그러나 그 트릭으로 우리는 중간 결과에 대한 목록을 설정하고 “목록을 통해”진행합니다.

fib n = (xs!!(n-1)) + (xs!!(n-2)) where xs = 0:1:map fib [2..]

트릭은 해당 목록을 생성하고 해당 목록이를 호출하는 사이에 가비지 수집을 통해 사라지지 않도록하는 것 fib입니다. 이를 달성하는 가장 쉬운 방법 은 목록의 이름 을 지정 하는 것입니다. “네가 이름을 지으면 그대로 남아있을 것이다.”

첫 번째 버전은 단형 상수를 정의하고 두 번째 버전은 다형성 함수를 정의합니다. 다형성 함수는 제공해야 할 다른 유형에 대해 동일한 내부 목록을 사용할 수 없으므로 공유 , 즉 메모가 없습니다.

첫 번째 버전에서 컴파일러는 상수 하위 표현식 ( )을 제거하고이를 별도의 공유 가능한 엔티티로 만드는 등 관대map fib' [0..] 하지만 그렇게 할 의무는 없습니다. ^{실제로 우리 가 자동으로 수행하는 것을 원하지 않는 경우가 있습니다.}

( 편집 🙂 다음 재 작성을 고려하십시오.

fib1 = f                     fib2 n = f n                 fib3 n = f n          
 where                        where                        where                
  f i = xs !! i                f i = xs !! i                f i = xs !! i       
  xs = map fib' [0..]          xs = map fib' [0..]          xs = map fib' [0..] 
  fib' 1 = 1                   fib' 1 = 1                   fib' 1 = 1          
  fib' 2 = 1                   fib' 2 = 1                   fib' 2 = 1          
  fib' i=fib1(i-2)+fib1(i-1)   fib' i=fib2(i-2)+fib2(i-1)   fib' i=f(i-2)+f(i-1)

따라서 실제 이야기는 중첩 된 범위 정의에 관한 것 같습니다. 첫 번째 정의에는 외부 범위가 없으며 세 번째는 외부 범위를 호출하지 않고 fib3동일한 수준 을 호출하도록주의 합니다 f.

의 값에 따라 (이론상) 다르게 정의 될 수fib2 있기 때문에 각각의 새로운 호출은 중첩 된 정의를 새로 만드는 것 같습니다 ( 이를 지적한 Vitus와 Tikhon에게 감사드립니다). 첫 번째 (고화질)로 더 없다 에 의존하고, 세 번째에 의존하지만 각각 별도의 호출이 로 호출 이 특정 호출 내부와 동일한 수준의 범위에서만 호출 정의에주의 인 동일하므로, 도착 해당 호출에 재사용 (즉 공유)됩니다 .nnfib3ffib3xsfib3

그러나 컴파일러가 위의 모든 버전의 내부 정의가 실제로 외부 바인딩과 독립적 이라는 것을 인식하는 것을 배제하지 않고 n결국 람다 리프팅 을 수행하여 전체 메모 화 (다형성 정의 제외)를 수행합니다. 사실 이것은 단형 유형으로 선언되고 -O2 플래그로 컴파일 될 때 세 가지 버전 모두에서 정확히 발생합니다. 다형성 유형 선언을 사용하면 fib3로컬 공유를 표시하고 fib2공유하지 않습니다.

궁극적으로 컴파일러 및 사용 된 컴파일러 최적화, 테스트 방법 (GHCI에서 파일로드, 컴파일 여부, -O2 사용 여부, 독립 실행 형), 모노 모픽 또는 다형성 유형을 가져 오는지 여부에 따라 동작이 수행 될 수 있습니다. 완전히 변경-로컬 (호출 당) 공유 (즉, 각 호출에 대한 선형 시간), 메모 (즉, 첫 번째 호출에 선형 시간, 후속 호출에 동일하거나 더 작은 인수가있는 후속 호출에 0 시간)를 표시하는지 또는 전혀 공유하지 않는지 ( 지수 시간).

짧은 대답은 컴파일러라는 것입니다. 🙂

답변

fib :: (Num n) => Int -> n

fib :: Int -> Integer

fib = zipWith (+) (0:(1:fib)) (1:fib)

zipWith :: (a->b->c) -> [a]->[b]->[c]
zipWith op (n1:val1) (n2:val2) = (n1 + n2) : (zipWith op val1 val2)
zipWith _ _ _ = []

print $ take 100 fib

[1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657,2111485077978050,3416454622906707,5527939700884757,8944394323791464,14472334024676221,23416728348467685,37889062373143906,61305790721611591,99194853094755497,160500643816367088,259695496911122585,420196140727489673,679891637638612258,1100087778366101931,1779979416004714189,2880067194370816120,4660046610375530309,7540113804746346429,12200160415121876738,19740274219868223167,31940434634990099905,51680708854858323072,83621143489848422977,135301852344706746049,218922995834555169026,354224848179261915075,573147844013817084101]