[Haskell-cafe] Dynamic Programming with Data.Vector

[Myles C. Maxfield]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120916/1e1e4138/attachment.htm>