[Haskell-cafe] Dynamic Programming with Data.Vector

[Myles C. Maxfield]

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 <
myles.maxfield at gmail.com> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120916/03a07bb2/attachment.htm>