Someone replied saying that I could use a HashMap and a fold to do this, and that solution should work quite well.<div><br></div><div>Bonus points if there&#39;s a solution without the space overhead of a hashmap :-) I&#39;m hoping for an unboxed vector.</div>

<div><br></div><div>--Myles<br><br><div class="gmail_quote">On Sun, Sep 16, 2012 at 12:40 PM, Myles C. Maxfield <span dir="ltr">&lt;<a href="mailto:myles.maxfield@gmail.com" target="_blank">myles.maxfield@gmail.com</a>&gt;</span> wrote:<br>

<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">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" target="_blank">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" target="_blank">http://hackage.haskell.org/packages/archive/vector/0.9.1/doc/html/Data-Vector.html#g:6</a></div>
</blockquote></div><br></div>