使用递归进行记忆

Question

我试图理解Haskell实现的memoization,但我不知道它是如何工作的:

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

首先,我甚至不明白为什么'map'函数得到三个参数(函数 - fib,list [0 ..]和||),而不是两个必须如何做.

更新:

我试图重写代码,但得到不同的结果:

f' :: (Int -> Int) -> Int -> Int
f' mf 0 = 0
f' mf 1 = 1
f' mf n = mf(n - 2) + mf(n - 1)

f'_list :: [Int]
f'_list = map (f' faster_f') [0..]

faster_f' :: Int -> Int
faster_f' n = f'_list !! n

为什么？我的推理中有任何错误吗？

Answer 1

第一:Haskell支持运算符部分.所以(+ 2)等于\ x -> x + 2.这意味着表达式map等于\ x -> map fib [0..] !! x.

其次,它是如何工作的:这是利用Haskell的按需调用评估策略(它的懒惰).

最初,map不会评估由此产生的列表.然后,当您需要访问某个特定索引时,将评估到该点为止的所有元素.但是,一旦评估了一个元素,它就不会再次被评估(只要你指的是同一个元素).这就是给你记忆的东西.

基本上,Haskell的懒惰评估策略涉及记忆强制值.这个memoized fib函数只依赖于这种行为.

这里"强制"一个值意味着评估一个称为thunk的延迟表达式.因此,列表基本上最初存储为列表的"承诺",并强制它将"承诺"转换为实际值,并将"承诺"转换为更多值."承诺"只是雷声,但我希望把它作为一个承诺更有意义.

我简化了一点,但这应该澄清实际的memoization如何工作.