使用 Data.Vector 进行动态规划
我正在使用 Data.Vector,目前需要计算向量的内容以用于计算加密哈希 (Sha1)。我创建了以下代码。
dynamic :: a -> Int -> (Int -> Vector a -> a) -> Vector a
dynamic e n f =
let
start = Data.Vector.replicate n e
in step start 0
where
step vector i = if i==n then vector
else step (vector // [(i,f i vector)]) (i+1)
我创建了这个,以便填充向量的函数 f 可以访问部分向量 一路上的结果。当然,像这样的东西一定已经存在于 Data.Vector 中,不是吗?
问题陈述如下:您要解决一个动态规划问题,其最终结果是一个数组。您知道数组大小,并且有一个递归函数来填充它。
am using Data.Vector and am currently in need of computing the contents of a vector for use in computing a cryptographic hash(Sha1). I created the following code.
dynamic :: a -> Int -> (Int -> Vector a -> a) -> Vector a
dynamic e n f =
let
start = Data.Vector.replicate n e
in step start 0
where
step vector i = if i==n then vector
else step (vector // [(i,f i vector)]) (i+1)
I created this so that the function f filling out the vector has access to the partial
results along the way. Surely something like this must already exist in Data.Vector, no?
The problem statement is the following: You are to solve a dynamic programming problem where the finished result is an array. You know the size of the array size and you have a recursive function for filling it out.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(2)
您可能已经见过函数
generate
,它采用大小n
和类型为Int ->; 的函数
,然后生成大小为f
。 an
的向量 a
。您可能没有意识到,在使用此函数时,您实际上可以访问部分结果。我的意思是说,在传递给
generate
的函数中,您可以引用您正在定义的向量,并且由于 Haskell 的惰性,它会正常工作(除非您这样做,以便不同的项目当然,矢量的大小以循环方式相互依赖)。示例:
tenFibs
现在是包含前 10 个斐波那契数的向量。You probably already saw the function
generate
, which takes a sizen
and a functionf
of typeInt -> a
and then produces aVector a
of sizen
. What you probably weren't aware of is that when using this function you actually do have access to the partial results.What I mean to say is that inside the function you pass to
generate
you can refer to the vector you're defining and due to Haskell's laziness it will work fine (unless you make it so that the different items of the vector depend on each other in a circular fashion, of course).Example:
tenFibs
is now a vector containing the first 10 Fibonacci numbers.也许您可以使用 Data.Vector 的扫描功能之一?
http://hackage. haskell.org/packages/archive/vector/0.6.0.2/doc/html/Data-Vector.html#32
Maybe you could use one of Data.Vector's scan functions?
http://hackage.haskell.org/packages/archive/vector/0.6.0.2/doc/html/Data-Vector.html#32