haskell - 函数式语言中的动态编程

Question

我学习haskell。我遇到了无法保存中间计算步骤的问题。感觉没效果。如何在函数式编程中使用动态编程？

Answer 1

我在 [in Haskell] 中遇到无法保存中间计算步骤的问题。

我不知道你用什么资源来学习它，但它们显然不是最好的。

例如：

let 
    intermediate = {- calculation step -}
in ...

将计算步骤的结果保存在intermediate. （更好：它将变量绑定intermediate到值。）

此外，引用相关的维基百科条目：

在数学、计算机科学和经济学中，动态规划是一种通过将复杂问题分解为更简单的子问题来解决复杂问题的方法。它适用于表现出重叠子问题[1]和最优子结构（如下所述）的性质的问题。在适用时，该方法比简单方法花费的时间要少得多。

动态规划背后的关键思想非常简单。一般来说，要解决一个给定的问题，我们需要解决问题的不同部分（子问题），然后将子问题的解决方案结合起来，达到一个整体的解决方案。通常，许多这些子问题实际上是相同的。动态规划方法试图只解决每个子问题一次，从而减少计算次数：一旦计算了给定子问题的解决方案，它就会被存储或“记忆化”：下次需要相同的解决方案时，它简直是抬头。当重复子问题的数量作为输入大小的函数呈指数增长时，这种方法特别有用。

很明显，Haskell 很好地支持了这种解决问题的方式。例如，在最简单的情况下，可以随身携带一张地图，以保存已经解决的子问题及其解决方案。更高级的方法可以使用 State Monad。等等。