函数语言中的动态编程

Question

我学习哈斯克尔.我遇到的问题是我无法保存中间计算步骤.感觉无效.如何在函数式编程中使用动态编程？

Answer 1

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

我不知道你曾经学过什么资源,但他们显然不是最好的.

例如:

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

保存计算步骤的结果intermediate.(更好:它将变量绑定intermediate到值.)

此外,引用相关的维基百科条目:

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

动态编程背后的关键思想非常简单.一般来说,为了解决给定的问题,我们需要解决问题的不同部分(子问题),然后结合子问题的解决方案来达到整体解决方案.通常,这些子问题中的许多都是相同的.动态编程方法只寻求解决每个子问题一次,从而减少计算次数:一旦计算出给定子问题的解,就存储或"备忘":下次需要相同的解决方案时,只是抬起头来.当重复子问题的数量随着输入的大小呈指数增长时,这种方法特别有用.

很明显,这种问题解决方式很好地得到了Haskell的支持.例如,在最简单的情况下,可以携带地图,这可以保留已经解决的子问题及其解决方案.更先进的方法可以使用State Monad.等等.