Memoizing`地圖F`調用

Question

我明白這個記憶化是如何工作的

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

但我怎麼能memoize的這個功能，它使用上述功能。

fibsFor :: [Int] -> [Int] 
fibsFor xs = map fib xs 

如何使fib的每個調用使用相同的緩存？

Answer 1

它是使用相同的「緩存」。對於相同的參數，通知fib從不計算兩次。

import Debug.Trace 

fib :: Int -> Int 
fib = (map (fib' . (\i -> trace ("fib called on " ++ show i) i)) [0..] !!) 
    where fib' 1 = 1 
      fib' 2 = 1 
      fib' n = fib (n-2) + fib (n-1) 

fibsFor :: [Int] -> [Int] 
fibsFor xs = map fib xs 


*Main> fibsFor [5, 10, 20] 
[fib called on 5 
fib called on 3 
fib called on 1 
fib called on 2 
fib called on 4 
5,fib called on 10 
fib called on 8 
fib called on 6 
fib called on 7 
fib called on 9 
55,fib called on 20 
fib called on 18 
fib called on 16 
fib called on 14 
fib called on 12 
fib called on 11 
fib called on 13 
fib called on 15 
fib called on 17 
fib called on 19 
6765]