Van*_*ril 42 haskell functional-programming dynamic-programming
Haskell和其他函数式编程语言是在不维护状态的前提下构建的.我还不熟悉函数式编程的工作原理和概念,所以我想知道是否有可能以FP方式实现DP算法.
可以使用哪些函数式编程结构来做到这一点？
luq*_*qui 17
这样做的常见方法是通过懒惰的记忆.在某种意义上,递归的斐波纳契函数可以被认为是动态编程,因为它计算重叠子问题的结果.我意识到这是一个疲惫的例子,但这是一种品味.它使用data-memocombinators库进行延迟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是memoized版本,fib'只是"暴力"问题,但使用memoized计算其子问题fib.其他DP算法使用不同的备忘录结构以相同的风格编写,但同样的想法是以简单的功能方式计算结果并进行记忆.
编辑:我终于放弃并决定提供一个可记忆的类型类.这意味着现在便于记忆:
import Data.MemoCombinators.Class (memoize)
fib = memoize fib'
where
fib' :: Integer -> Integer -- but type sig now required
...
需要遵循类型的Instaead,你可以做memoize任何事情.如果你喜欢,你仍然可以使用旧的方式.
kow*_*wey 17
Rabhi和Lapalme的算法:函数式编程方法有一个很好的章节,它说明了一些FP概念正在使用,即 高阶函数和惰性求值.我认为我可以重现其高阶函数的简化版本.
它的简化之处在于它仅适用于将Int作为输入并将Int作为输出生成的函数.因为我们以两种不同的方式使用Int,所以我将为它们创建"Key"和"Value"的同义词.但是不要忘记,因为这些是synonynms,完全可以使用Keys和Values,反之亦然.它们仅用于可读性.
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])
让我们稍微剖析一下这个功能.
首先,这个功能是做什么的？ 从类型签名我们可以看到它以某种方式操纵表.实际上,第一个参数"compute"是一个函数(因此dynamic是一个"高阶"函数),它从表中产生某种值,而第二个参数只是某种上界,告诉我们在哪里停止.作为输出,"动态"功能为我们提供了某种表格.如果我们想得到一些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 - >表 - > ...对 - >在像\ coord这样的匿名函数中 - > ...如果你对这些不熟悉,它们可能会妨碍它们.
要解决的另一个先决条件是此查找表.我们不想担心它是如何工作的,但我们假设我们可以从键值对列表中创建它们,并在其中查找条目:
newTable :: [(k,v)] -> Table v k
findTable :: Table v k -> k -> v
这里要注意三件事:
最后,这个功能如何实际起作用？ 这里发生了什么？我们可以放大一点功能,
t = newTable (map (\coord -> (coord, compute t coord)) [0..bnd])
并有条不紊地撕开它.从外面开始,我们得到了t = newTable(...),这似乎告诉我们,我们正在从某种列表构建一个表.无聊.列表怎么样？
map (\coord -> (coord, compute t coord)) [0..bnd]
在这里,我们得到了更高阶的映射函数,从0到bnd的列表向下走,并生成一个新的列表作为结果.要计算新列表,它使用函数\ coord - >(coord,compute t coord).请记住上下文:我们正在尝试从键值对构建表,因此如果您研究元组,则第一部分coord必须是键,第二部分compute t coord必须是值.第二部分是令人兴奋的事情.让我们进一步放大
compute t coord
我们正在建立一个来自键值对的表,我们插入这些表的值来自于运行"compute t coord".我之前没有提到过的一点是,compute会将一个表和一个键作为输入,并告诉我们应该将哪些值插入表中,换句话说,我们应该将哪个值与该键相关联.然后,将其重新用于动态编程的想法是,计算函数使用表中的先前值来计算我们应该插入的新值.
就这样!要在Haskell中进行动态编程,我们可以通过使用查找表中先前值的函数将值连续插入单元格来构建某种表.容易,对吧？......或者是吗？
也许你和我有过类似的经历.所以我想分享我目前正在努力解决这个问题的进展.当我第一次阅读这个功能时,它似乎具有一种直观的感觉,而我并没有多想它.然后我仔细阅读并做了一些双重拍,等什么？!这怎么可能有效呢？再来看看这段代码.
compute t coord
为了计算给定单元格的值并填充表格,我们传入t,即我们试图首先创建的表格.如果您指出函数式编程是关于不变性的,那么使用我们尚未计算的值的这项业务怎么可能起作用呢？如果你掌握了一点FP,你可能会像我一样问自己,"这是一个错误吗？",这不应该是"折叠"而不是"地图"吗？
这里的关键是懒惰的评价.可以从自身的位中创建不可变值的一点点魔法都归结为懒惰.作为一种长期黄腰带的Haskeller,我仍然觉得懒惰的概念有点莫名其妙.所以我必须让其他人接管这里.
与此同时,我只是告诉自己这没关系.我满足于将桌子视为一种点,其中有许多箭头从中伸出.以fib为例:
o
|
|--0--> 1
|
|--1--> 1
|
|--2--> 2
|
|--3--> 2
.
.
.
我们还没有看到的表位是未被发现的领域.当我们第一次走下清单时,它们都是未被发现的
o
.
.
.
当我们想要计算第一个值时,我们不需要知道关于该表的任何信息,因为i <= 1.
helper t i =
if i <= 1
then i
else findTable t (i-1) + findTable t (i-2)
o
|
|--0--> 1
.
.
.
当我们想要计算连续值时,我们总是只回顾已经发现的表格部分(动态编程,嘿嘿!).要记住的关键是我们在这里100%使用不可变值,除了懒惰之外没有花哨的技巧."t"实际上意味着表,而不是"在迭代42处当前状态的表".只是我们只发现表的位,告诉我们当我们实际要求它时,42对应的值是什么.
希望与StackOverflow上的其他人一起,你会比我更远,而不是模糊地咕>>"嗯呀,懒惰的东西或其他东西"这真的不是什么大问题:-)
Art*_*yom 10
如果要使用带有2个或3个参数的DP(例如,处理字符串时),可以使用不可变数组:
import Data.Array.IArray
answer :: String -> Int
answer s = table ! (1, l)
where
l = length s
--signatyres are needed, because GHC doesn't know what kind of Array we need
--string is stored in Array because we need quick access to individual chars
a :: Array Int Char
a = listArray (1, l) s
table :: Array (Int, Int) Int
table = listArray ((1, 1), (l, l)) [f i j | i <- [1..l], j <- [1..l]]
f i j | i > j = 0
| i == j = 1
| (a ! i) == (a ! j) = 2 + table ! (i+1, j-1)
| otherwise = maximum [table ! (i+1, j), table ! (i, j-1)]
该代码解决了以下任务:给定一个字符串S,找到最大长度为S的子序列,这将是一个palyndrome(子序列不需要是连续的).
基本上,'f'是resursive函数,array'table'是所有可能值的矩阵.因为Haskell是惰性的,所以只需要计算"f"的答案值.换句话说,这是带有memoization的递归.所以使用Data.Memocombinators,它是一样的,但已经由别人写了:)