Myles C. Maxfield | 16 Sep 21:40 2012
Picon

Dynamic Programming with Data.Vector

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.

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Myles C. Maxfield | 16 Sep 22:34 2012
Picon

Re: Dynamic Programming with Data.Vector

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.


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Roman Leshchinskiy | 17 Sep 15:07 2012
Picon
Picon

Re: Dynamic Programming with Data.Vector

Myles C. Maxfield wrote:
>
> 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.

Indeed there is, it's called constructN (or constructrN if you want to
construct it right to left).

Roman
Myles C. Maxfield | 17 Sep 18:42 2012
Picon

Re: Dynamic Programming with Data.Vector

Aha there it is! Thanks so much. I didn't see it because it's under the "Unfolding" section instead of the "Construction" section.


--Myles

On Mon, Sep 17, 2012 at 6:07 AM, Roman Leshchinskiy <rl <at> cse.unsw.edu.au> wrote:
Myles C. Maxfield wrote:
>
> 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.

Indeed there is, it's called constructN (or constructrN if you want to
construct it right to left).

Roman




_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Gmane