Haskell 中的动态编程。这是正确的方法吗(?)

Question

Haskell 不允许改变全局变量，这是动态编程的关键概念，所以我想出了一个解决方案。 这依赖于 Haskell 的惰性求值和无限列表 我的问题是线性时间和空间效率吗（？）

这是我的解决方案

 fibs = [0,1] ++ [n | i <- [2..], let n = fibs !! (i-1) + fibs !! (i-2)]

我们将前 2 个 fibs 数字（即 0、1）与潜在的无限列表相加。 该列表有一个索引生成器（无限）。 我们声明一个局部变量

n = fibs !! (i-1) + fibs !! (i-2)

所以我尝试使用旧结果来获得新结果。 现在这样节省空间吗（？）

Answer 1

您的解决方案是二次时间的，但大约尽可能节省空间，按照评论中的建议提供给它一个单态类型签名。二次时间复杂度来自于重复使用

!!

进行索引；该函数是线性时间，它用于线性长度循环，给出顶级二次运行时间。有多种技巧可以解决这个问题。一个特别漂亮（也是标准）的方法是使用 zip 获取列表的相邻元素。

fibs = [0,1] ++ zipWith (+) fibs (tail fibs)

如果空间效率足够重要，以至于开始担心渐进中的常量，那么您将需要使用更大的长度来使其更好——例如，越来越长的数组列表或类似的东西。