Data.Memocombinators가 여분의 변수가있을 때 사례를 잡아 내지 못함

Question

아래의 두 가지 기능을 고려하십시오. DP 캐시 히트 또는 누락을 표시하기 위해 traceShow이 포함되었습니다. 첫 번째 것은 MemoCombinators documentation에서 파종되었습니다. 두 번째는 나 자신을 만들었다.

import Data.MemoCombinators as Memo 
import Debug.Trace 

fib :: Int -> Int 
fib = Memo.integral fib' 
    where 
     fib' :: Int -> Int 
     fib' 0 = traceShow 0 $ 0 
     fib' 1 = traceShow 1 $ 1 
     fib' n = traceShow n $ fib (n-1) + fib (n-2)  

brokenFib :: a -> Int -> Int 
brokenFib a = Memo.integral brokenFib' 
    where 
     brokenFib' :: Int -> Int 
     brokenFib' 0 = traceShow 0 $ 0 
     brokenFib' 1 = traceShow 1 $ 1 
     brokenFib' n = traceShow n $ brokenFib [] (n-1) + brokenFib [] (n-2) 

fib는 DP를 활용하지만, 여분의 변수가 어떻게 든 그것을 엉망으로해야 의미하지 brokenFib 않습니다. 두 인수 함수의 인수 중 하나만을 DP로 지정하려는 시나리오를 작성하는 것은 어렵지 않지만 추가 변수가 brokenFib을 어지럽히는 방법을 찾지 않고는 수행 할 수 없습니다. 어떤 충고?

편집 : user6655594 @에 의해 주어진 두 번째 솔루션의

구현 : 그것은 하나 DP를 잡을하지 않습니다

brokenFib :: a -> Int -> Int 
brokenFib = Memo.memoSecond Memo.integral brokenFib' 
    where 
     brokenFib' :: a -> Int -> Int 
     brokenFib' _ 1 = traceShow 1 $ 1 
     brokenFib' _ 2 = traceShow 1 $ 1 
     brokenFib' _ n = traceShow n $ (brokenFib [] (n-1)) + brokenFib [] (n-2) 

, 문서 ("함수의 두 번째 인수를 Memoize")이 시사하는 그것을해야합니다.

Answer 1

음을 사용할 수 있습니다, 그것은 바로이 질문 전에 #haskell 삼년에 논의되었다 밝혀졌습니다.

• efie : 15695230 (참조 http://lpaste.net/87973을 lpaste)
• INT-E : 15695262
• efie : 15695288
• INT-E : 15695302

다음 채팅 이벤트에서보세요

int-e의 발언에 따르면, 그 memoSecond integral f 그 자체가 인 것 같습니다. usefu 엘.제 생각에는 당신이 두 번째 인수가 어떻게 memoized되어야 하는지를 지정할 수 있도록 사용하기위한 것입니다. 즉, 두 함수 인수 모두에 을 항상 메모해야하고 두 번째 인수를 메모하기 위해 전략을 지정할 수 있도록 memoSecond이 제공됩니다. 따라서, INT-E는 같은 제안 : 물론

integral (memoSecond integral f) 

을 각 integral 다른 메모이 제이션 전략으로 대체 될 수있다.

또한, 실제로 당신이 기능 를 작성하고 실행할 whenter이 ghci를 사용하거나 GHC 어떤 최적화 레벨을 사용하여 컴파일하는 방법에 따라 달라질 수 있습니다 무슨.

이 프로그램을 고려 : (. 다른 모든 라인이 동일)

import qualified 
    Data.MemoCombinators as Memo 
import Debug.Trace 

afib :: Char -> Int -> Int 
afib _ = bfib 
    where 
    bfib = Memo.integral cfib 
    cfib n | trace msg False = undefined 
     where msg = "cfib at " ++ show n 
    cfib 1 = 1 
    cfib 2 = 2 
    cfib n = bfib (n-1) + bfib (n-2) 

main = do print (afib 'x' 5); print (afib 'x' 6) 

및 라인 afib _ = bfib이 afib = \_ -> bfib로 변경됩니다 두 번째 버전을 AFIB 당신이 실행하는 방법에 따라 달라질 수 있습니다 memoized 여부

/컴파일 :

  afib _ = bfib | afib = \_ -> bfib 
      ---------------|------------------- 
ghci  NOT MEMOIZED | MEMOIZED 
runhaskell NOT MEMOIZED | MEMOIZED 
ghc   NOT MEMOIZED | MEMOIZED 
ghc -O2  MEMOIZED  | MEMOIZED 

그래서,이 나타납니다이 경우에 당신이,536,913을 보장하기 위해 두 번째 양식을 사용한다메모.

Answer 2

차이점은 fib은 변경되지 않는 값입니다. 메모를 작성한 함수이며 메모 값은 호출간에 공유됩니다.

한편 brokenFib은 a 유형의 값을 가진 각 호출에 대해 다른 값과 메모 값을 공유하지 않는 새로운 메모 기능을 만듭니다.

당신은 몇 가지 옵션 (I 그들 중 하나를 테스트하지 않았고 나는 패키지가 익숙하지 않다)이 있습니다

brokenFib = memoizeSecond integral brokenFib' 
    ... 

같은 두 번째 인수, 뭔가를 memoize하는

• 사용 memoSecond을

  비록 첫 번째 인수가 처리되는 방식을 문서에서 설명하지는 않습니다.

• 가능하면 두 인수를 모두 memo2으로 메모하십시오. 유형 a의 첫 번째 인수는 전체 호출에 걸쳐 동일한 경우

• , 당신은

  brokenFib a = go 
      where 
      go = integral go' 
      go' = ... -- and calls 'go', not 'brokenFib' for recursive calls!