记忆化递归

Question

我想了解Haskell realization of 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'功能得到三个参数（函数 - 纤维，列表[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的call-by-need评估策略（它的懒惰）。

最初，由map产生的列表未被评估。然后，当你需要到达某个特定的索引时，到目前为止的所有元素都会被评估。然而，一旦一个元素被评估，它不会再被评估（只要你指的是相同的元素）。这是给你记忆的东西。

基本上，Haskell的懒惰评估策略涉及记忆强制值。这个被记忆的fib函数只是依赖于该行为。

这里“强制”一个值意味着评估称为thunk的延迟表达式。因此，这个清单基本上是作为一个清单的“承诺”存储起来的，强迫它将“承诺”转化为实际价值，并承诺为更多价值。这些“承诺”只是一个沉重的代价，但我希望称它为一个承诺更有意义。

我简化了一下，但是这应该说明实际的memoization是如何工作的。

Answer 2

map这里不带三个参数。

(map fib [0..] !!) 

部分适用（切片）的功能与(!!)map fib [0..]，列表，作为其第一个（左手）参数。

Answer 3

也许是更清晰的写它：

memoized_fib n = (map fib [0..]) !! n 

所以它只是从列表中取n个元素，并且该列表懒洋洋地评估。

这个operator section东西和正常的部分应用完全一样，但是对于中缀操作符。事实上，如果我们写一个普通函数，而不是!!缀操作相同的形式，看看它的样子：

import Data.List (genericIndex) 

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