Someone replied saying that I could use a HashMap and a fold to do this, and that solution should work quite well. Bonus points if there's a solution without the space overhead of a hashmap :-) I'm hoping for an unboxed vector. --Myles On Sun, Sep 16, 2012 at 12:40 PM, Myles C. Maxfield < myles.maxfield@gmail.com> wrote:

Hello,

I've been writing dynamic programming (dp) algorithms in imperative languages for years, and I was thinking recently about how to use it in a Haskell context. In particular, I want to write a function that takes an ordered collection of items and produces a new item to insert into the ordered collection.

The most straightforward way to do this would be to use a list, something like the following:

recurse :: [Integer] -> [Integer] recurse l = newValue : recurse (take (length l + 1) infiniteList) where newValue = ...

infiniteList :: [Integer] infiniteList = initialList ++ recurse initialList where initialList = ...

solution :: Integer solution = infiniteList !! 5

I'm assuming that this can run fast because I'm assuming the 'take' function won't actually duplicate the list ([1] doesn't actually list the running time of 'take') Is this a correct assumption to make?

Secondarily, and most importantly for me, I'm curious about how to make this fast when the computation of 'newValue' requires random access to the inputted list. I'm assuming that I would use Vectors instead of lists for this kind of computation, and [2] describes how I can use the O(1) 'slice' instead of 'take' above. However, both of Vector's cons and snoc functions are O(n) which defeats the purpose of using this kind of algorithm. Obviously, I can solve this problem with mutable vectors, but that's quite inelegant.

Overall, I'm looking for a function, similar to Data.Vector's 'generate' function, but instead of the generation function taking the destination index, I'd like it to take the elements that have previously been constructed. Is there such a function? If there isn't one, is this kind of function feasible to write? If such a function doesn't exist and is feasible to write, I'd be happy to try to write and contribute it.

[1] http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-List.html#g:... [2] http://hackage.haskell.org/packages/archive/vector/0.9.1/doc/html/Data-Vecto...