Rabhi 和 Lapalme 的算法：一种函数式编程方法对此有一个很好的章节，说明了一些正在使用的 FP 概念，即高阶函数和懒惰的评价。我认为我可以重现其高阶函数的简化版本。

它的简化在于它只适用于将 Int 作为输入并产生 Int 作为输出的函数。因为我们以两种不同的方式使用 Int，所以我将为它们创建同义词“Key”和“Value”。但是不要忘记，因为这些是同义词，所以完全可以使用键和值，反之亦然。它们仅用于提高可读性。

让我们稍微剖析一下这个函数。

首先，这个函数有什么作用？从类型签名我们可以看出它以某种方式操纵表格。实际上，第一个参数“compute”是一个函数（因此 dynamic 是一个“高阶”函数），它从表中产生某种值，第二个参数只是某种上限，告诉我们在哪里停止。作为输出，“动态”函数为我们提供了某种表格。如果我们想得到一些对 DP 友好的问题的答案，我们运行“动态”，然后从我们的表中查找答案。

要使用这个函数来计算斐波那契，我们可以像这样运行它

另一个需要解决的先决条件是这个查找表。我们不想担心它是如何工作的，但让我们假设我们可以从键值对列表中创建它们并在其中查找条目：

这里要注意三点：

最后，这个函数实际上是如何工作的？这是怎么回事？我们可以放大一点函数的内容，

并有条不紊地撕开它。从外到内，我们得到了 t = newTable (...)，这似乎告诉我们我们正在从某种列表中构建一个表。无聊的。清单呢？

这里我们有更高阶的 map 函数从 0 到 bnd 并生成一个新列表作为结果。要计算新列表，它使用函数 \coord -> (coord, compute t coord)。 请记住上下文：我们正在尝试从键值对构建一个表，因此如果您研究元组，第一部分 coord 必须是键，第二部分计算 t coord 必须是值。第二部分是事情变得令人兴奋的地方。让我们再放大一点

我们正在从键值对构建一个表，我们插入这些表的值来自运行“计算 t 坐标”。我之前没有提到的是，compute 将一个表和一个键作为输入，并告诉我们应该将什么值插入表中，换句话说，我们应该将什么值与该键关联。然后，将其带回动态编程的想法是，计算函数使用表中的先前值来计算我们应该插入的新值。

仅此而已！为了在 Haskell 中进行动态编程，我们可以通过使用从表中查找先前值的函数将值连续插入单元格来构建某种表。简单，对吧？...或者是吗？

也许你和我有类似的经历。所以我想分享一下我目前在这个功能上的进展。当我第一次阅读这个功能时，它似乎有一种直观的感觉，我并没有多想。然后我仔细阅读并做了一种双重考虑，等等什么？！这怎么可能起作用？在这里再看一下这段 sn-p 代码。

为了计算给定单元格的值并填充表格，我们传入 t，这是我们首先尝试创建的表格。如果正如您所指出的那样，函数式编程是关于不变性的，那么使用我们尚未计算的值的这种业务如何可能起作用？如果你有一点 FP，你可能会像我一样问自己，“这是一个错误吗？”，这不应该是“折叠”而不是“地图”吗？

这里的关键是惰性求值。可以从自身的位中创建不可变价值的一点点魔法都归结为懒惰。作为一个长期持有黄带的 Haskeller，我仍然觉得懒惰的概念有点莫名其妙。所以我得让其他人来接管这里。

与此同时，我只是告诉自己这没关系。我满足于将表格想象成一个点，上面有很多箭头。以fib为例：

我们还没有看到的表格部分是未被发现的领域。当我们第一次浏览列表时，一切都没有被发现

当我们想要计算第一个值时，我们不需要知道更多关于表的信息，因为 i

当我们想要计算连续值时，我们总是只回顾表中已经发现的部分（动态编程，嘿嘿！）。要记住的关键是我们在这里 100% 使用不可变值，除了懒惰之外没有花哨的技巧。 “t”实际上是指表，而不是“在迭代 42 时处于当前状态的表”。只是当我们实际请求它时，我们才发现表中的位告诉我们对应于 42 的值是什么。

希望与 * 上的其他人一起，你会比我走得更远，不要含糊地说“嗯，是的，懒惰什么的”这真的没什么大不了的 :-)