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

问题描述

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

Haskell and other functional programming languages are built around the premise of not maintaining state. I'm still new to how functional programming works and concepts in it, so I was wondering if it is possible to implement DP algorithms in an FP way.

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

What functional programming constructs can be used to do that?

推荐答案

执行此操作的常用方法是通过延迟记忆.在某种意义上，递归斐波那契函数可以被认为是动态规划，因为它计算出重叠子问题的结果.我意识到这是一个累人的例子，但这里有一个味道.它使用 data-memocombinators 库来实现惰性记忆.

The common way to do this is via lazy memoization. In some sense, the recursive fibonacci function can be considered dynamic programming, because it computes results out of overlapping subproblems. I realize this is a tired example, but here's a taste. It uses the data-memocombinators library for lazy memoization.

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 算法以相同的风格编写，使用不同的备忘录结构，但相同的想法只是以简单的函数方式计算结果和记忆.

fib is the memoized version, and fib' just "brute forces" the problem, but computes its subproblems using the memoized fib. Other DP algorithms are written in this same style, using different memo structures, but the same idea of just computing the result in a straightforward functional way and memoizing.

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

Edit: I finally gave in and decided to provide a memoizable typeclass. That means that memoizing is easier now:

import Data.MemoCombinators.Class (memoize)

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

不需要跟随类型，你可以memoize任何东西.如果你喜欢，你仍然可以使用旧的方式.

Instaead of needing to follow the type, you can just memoize anything. You can still use the old way if you like it.

这篇关于动态规划算法如何在惯用的 Haskell 中实现?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！