动态规划算法如何在惯用的 Haskell 中实现？

Question

Haskell 和其他函数式编程语言都是围绕不维护状态的前提构建的。 我对函数式编程的工作原理和其中的概念仍然很陌生，所以我想知道是否可以以 FP 方式实现 DP 算法。

可以使用哪些函数式编程结构来做到这一点？

Answer 1

执行此操作的常见方法是通过惰性记忆。 从某种意义上说，递归斐波那契函数可以被视为动态规划，因为它计算重叠子问题的结果。我意识到这是一个令人厌倦的例子，但这里是一个品味。 它使用 data-memocombinators 库进行惰性记忆。

import qualified Data.MemoCombinators as Memo

fib = Memo.integral fib'
    where
    fib' 0 = 0
    fib' 1 = 1
    fib' n = fib (n-1) + fib (n-2)

fib

是记忆版本，

fib'

只是“强力”解决问题，但使用记忆的

fib

计算其子问题。 其他 DP 算法都是以相同的风格编写的，使用不同的备忘录结构，但都是以简单的函数方式计算结果并进行记忆的相同想法。

编辑：我最终屈服并决定提供一个可记忆的类型类。 这意味着现在记忆更容易了：

import Data.MemoCombinators.Class (memoize)

fib = memoize fib'
    where
    fib' :: Integer -> Integer  -- but type sig now required 
    ...

无需遵循类型，您可以直接

memoize

任何内容。 如果你喜欢的话，你仍然可以使用旧的方式。

Answer 2

Rabhi 和 Lapalme 的 算法：函数式编程方法 有一个很好的章节介绍了这一点，其中说明了一些 FP 概念的使用，即高阶函数和惰性求值。我认为我可以重现其高阶函数的简化版本。

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

type Key = Int
type Value = Int

dynamic :: (Table Value Key -> Key -> Value) -> Key -> Table Value Key
dynamic compute bnd = t
 where t = newTable (map (\coord -> (coord, compute t coord)) [0..bnd])

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

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

要使用此函数来计算斐波那契数列，我们将像这样运行它

fib = findTable (dynamic helper n) n
 where
  helper t i =
    if i <= 1
       then i
       else findTable t (i-1) + findTable t (i-2)

暂时不用太担心理解这个 fib 函数。 当我们探索“动态”时，它会变得更加清晰。

其次，我们需要了解哪些先决条件才能理解这个函数？我假设您或多或少熟悉语法，[0..x] 表示从 0 到 x 的列表， Int -> Table -> ... 等类型签名中的 -> 与类似匿名函数中的 ->