Динамическое программирование с 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, вы можете обращаться квектор, который вы определяете, и из-за лени Хаскелла он будет работать нормально (если вы не сделаете так, чтобы разные элементы вектора зависели друг от друга по кругу, конечно).

Пример:

import Data.Vector

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

tenFibs теперь является вектором, содержащим первые 10 чисел Фибоначчи.

Answer 2

Может быть, вы могли бы использовать одну из функций сканирования Data.Vector?http://hackage.haskell.org/packages/archive/vector/0.6.0.2/doc/html/Data-Vector.html#32