1

我已经意识到以下程序

fibMap :: [Integer] -> [Integer]                                                          
fibMap xs = 1 : 1 : (zipWith (+) xs $ tail xs)                                            
                                                                                          
fix :: (b -> b) -> b                                                                      
fix f = f $ fix f 

> take 100 $ fix fibMap

速度惊人。它比递归定义快得多：

fib 0 = 1                                                                                 
fib 1 = 1                                                                                 
fib k = fib (k-1) + fib (k-2)

> fib 100

我很难理解定点定义实际上归结为哪种程序算法。仅仅是因为 Haskell 的编译器做了一些巧妙的优化，还是它本质上很快？

让我们稍微解开固定点：

x = fix fibMap = fibMap $ fix fibMap 
= 1:1:(zipWith (+) y $ tail y) 
   where y = fix fibMap = fibMap $ fix fibMap

Haskell 编译器是否识别 x = y 和“short-fuse”？它会更多地了解列表 x，还是会从头开始重新计算 y 的所有内容？

我觉得短融合会产生一个快速的算法，而重新计算 y 会给出大致相当于递归算法的东西？

是否有任何技巧/思维方式可以更轻松地确定使用固定点的算法的复杂性？它对编译器的评估策略敏感吗？

4

1 回答 1

2

关键思想是共享工作。在朴素版本中，fib (n-2)从头开始计算两次 ( fib n = fib (n-1) + fib (n-2) = fib (n-2) + fib (n-2) + fib (n-3))。在列表版本中，参数xs表示递归调用，它被评估一次，使用两次。

fix fibMap = fibMap (fix fibMap)
           = let xs = fix fibMap in
             1 : 1 : zipWith (+) xs (tail xs)

思考这项工作的一种方法是将目标从“如何计算第 n 个斐波那契数”更改为“如何计算前 n 个斐波那契数的列表”。对于 n > 2：

  1. 前两个斐波那契数是 1 和 1；

  2. 剩余的 (n-2) 可以从第一个 (n-1) 斐波那契数中计算出来，方法是用自身压缩该列表。

它仍然是一种递归算法，但只有一个递归调用，这就是避免指数爆炸的方法。

事实上，根据上述定义，您可以通过等式推理正式证明take n (fix fibMap)(for n > 2) 的以下恒等式：

take n (fix fibMap)
  = let ys = take (n-1) (fix fibMap) in
    1 : 1 : zipWith (+) ys (tail ys)

上述算法进行了大约 n 次递归调用，并且对于每次调用，它都会压缩一个长度最多为 n 的列表，因此复杂度最多为二次 (O(n^2))，这实际上是一个紧界。

您可能期望线性复杂度界限 (O(n))，但为此您必须稍微调整算法。问题当然是每一步的“压缩”操作都会做很多多余的工作。

这是这两个定义之间的区别fix：

fix f = f (fix f)

和

fix f = let self = f self in self

它们在产生相同值的意义上是等价的，但它们在操作上有所不同：在某些情况下（例如这个），第二个执行效率更高。

在第一个定义中，当f需要它的参数时，它会fix f从头开始重新计算。

在第二个定义中，参数f是它自己的结果，所以当f需要它的参数时，它会使用它已经部分计算的结果。

现在在定义斐波那契数列的具体情况下，使用上述第一个版本的定义效率低下，因为它对（因此）fix进行了无数次调用：fibMapzipWith

fix fibMap = fibMap (fix fibMap) = fibMap (fibMap (fix fibMap)) = ...

而第二个版本fibMap只使用一次：

fiblist = let self = fibMap self in self

-- equivalent definition
fiblist = fibMap fiblist
于 2020-07-03T22:45:20.930 回答