使用 Data.Vector 进行动态规划

发布于 2024-09-18 00:26:09 字数 492 浏览 11 评论 0原文

我正在使用 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 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(2

复古式 2024-09-25 00:26:10

您可能已经见过函数 generate,它采用大小 n 和类型为 Int ->; 的函数 f。 a,然后生成大小为 n向量 a。您可能没有意识到,在使用此函数时,您实际上可以访问部分结果。

我的意思是说,在传递给 generate 的函数中,您可以引用您正在定义的向量,并且由于 Haskell 的惰性,它会正常工作(除非您这样做,以便不同的项目当然,矢量的大小以循环方式相互依赖)。

示例:

import Data.Vector

tenFibs = generate 10 fib
    where fib 0 = 0
          fib 1 = 1
          fib n = tenFibs ! (n-1) + tenFibs ! (n-2)

tenFibs 现在是包含前 10 个斐波那契数的向量。

You probably already saw the function generate, which takes a size n and a function f of type Int -> a and then produces a Vector a of size n. 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:

import Data.Vector

tenFibs = generate 10 fib
    where fib 0 = 0
          fib 1 = 1
          fib n = tenFibs ! (n-1) + tenFibs ! (n-2)

tenFibs is now a vector containing the first 10 Fibonacci numbers.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文