Dynamic programming with Data.Vector

Question

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.

Shouldn't every occurence of n in the last line actually be i? — sepp2k
– sepp2k, Commented Sep 7, 2010 at 13:58

sepp2k · Accepted Answer · 2010-09-09 00:09:22Z

8

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.

edited Sep 9, 2010 at 0:09

answered Sep 8, 2010 at 22:34

sepp2k

372k56 gold badges687 silver badges687 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

LennyStackOverflow · Accepted Answer · 2010-09-07 14:00:22Z

0

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

answered Sep 7, 2010 at 14:00

LennyStackOverflow

2,2381 gold badge19 silver badges22 bronze badges

Collectives™ on Stack Overflow

Dynamic programming with Data.Vector

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related