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 < [email protected]> 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:11 > [2] > http://hackage.haskell.org/packages/archive/vector/0.9.1/doc/html/Data-Vector.html#g:6 >
_______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
