Hello,<div><br></div><div>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.</div>
<div><br></div><div>The most straightforward way to do this would be to use a list, something like the following:</div><div><br></div><div><div>recurse :: [Integer] -> [Integer]</div><div>recurse l = newValue : recurse (take (length l + 1) infiniteList)</div>
<div> where newValue = ...</div><div><br></div><div>infiniteList :: [Integer]</div><div>infiniteList = initialList ++ recurse initialList</div><div> where initialList = ...</div><div><br></div><div>solution :: Integer</div>
</div><div>solution = infiniteList !! 5</div><div><br></div><div>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?</div>
<div><br></div><div>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.</div>
<div><br></div><div>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.</div>
<div><br></div><div>[1] <a href="http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-List.html#g:11">http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-List.html#g:11</a></div><div>[2] <a href="http://hackage.haskell.org/packages/archive/vector/0.9.1/doc/html/Data-Vector.html#g:6">http://hackage.haskell.org/packages/archive/vector/0.9.1/doc/html/Data-Vector.html#g:6</a></div>