Hello,<div><br></div><div>I&#39;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] -&gt; [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&#39;m assuming that this can run fast because I&#39;m assuming the &#39;take&#39; function won&#39;t actually duplicate the list ([1] doesn&#39;t actually list the running time of &#39;take&#39;) Is this a correct assumption to make?</div>

<div><br></div><div>Secondarily, and most importantly for me, I&#39;m curious about how to make this fast when the computation of &#39;newValue&#39; requires random access to the inputted list. I&#39;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) &#39;slice&#39; instead of &#39;take&#39; above. However, both of Vector&#39;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&#39;s quite inelegant.</div>

<div><br></div><div>Overall, I&#39;m looking for a function, similar to Data.Vector&#39;s &#39;generate&#39; function, but instead of the generation function taking the destination index, I&#39;d like it to take the elements that have previously been constructed. Is there such a function? If there isn&#39;t one, is this kind of function feasible to write? If such a function doesn&#39;t exist and is feasible to write, I&#39;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>