使用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和f类型的函数,Int -> a然后生成一个Vector a大小n.您可能不知道的是,在使用此功能时,您实际上可以访问部分结果.

我的意思是说,你传递给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个斐波纳契数的向量.