为什么它是一个记忆功能？

Question

有人可以向我解释,为什么下面的代码是memoization:

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

Answer 1

我假设你在问这个备忘录是怎么回事fib.fib本身只是一个普通的功能.真正的魔法发生在fib_mem = (map fib [0..] !!),记忆中fib.这个表达相当于说fib_mem x = (map fib [0..]) !! x.让我们分解一下,看看它在做什么:

• [0..]是一个无限的列表开始[0,1,2,3,..]和无限的继续无限.
• map fib [0..]适用fib于此列表的每个元素,生成一个列表,其中每个元素是与该元素的索引对应的斐波纳契数,因此例如8在索引处5.这是重要的一步 ; 它fib通过将其应用于每个数字来进行记忆,因此一旦特定索引处的值被强制,就不必重新计算它.
• 然后!!用于从列表中以适当的索引返回值.