arrays - 使用 Data.Vector 进行动态编程

Question

我正在使用 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 中肯定已经存在这样的东西，不是吗？

问题陈述如下:你要解决一个动态规划问题，其中完成的结果是一个数组。您知道数组大小，并且有一个递归函数来填充它。

Answer 1

您可能已经看到函数 generate，它采用大小 n 和类型为 Int -> a 的函数 f ，然后生成大小为 n 的 Vector 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 个斐波纳契数的向量。