haskell - 为什么它是内存功能？

Question

有人可以向我解释一下为什么下面的代码是记忆化的吗:

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通过将其应用于每个数字，因此一旦强制使用特定索引处的值，就不必重新计算。
• 然后!!用于从列表中适当的索引处获取值。