Converting Java-like 2D Dynamic Programing Matrix to Haskell

Question

I'm currently working with a dynamic programing algorithm in java, which uses a classic 2D matrix for back calculations. I'm trying my luck at converting it to a functional language like haskell, but it's proving beyond my match. Looking for any recommendations on what the solution might look like:

int[][] dynamic = new int[size][size];
for (int outer = 0; outer < size; j++){
    Arrays.fill(dynamic[outer], 0);
}

dynamic[0][0] = 1; 

for (int a = 0; a < size; a++){ 
   for (int b = a; b < size; b++){ 
      if (a == 0){
        dynamic[a+1][b+1] = dynamic[a][b] * 2;

        dynamic[a][b+1] = dynamic[a][b] * -1;
      } else{
        dynamic[a+1][b+1] = dynamic[a+1][b+1] + (dynamic[a][b] * 3);
        dynamic[a][b+1] = dynamic[a][b+1] + (dynamic[a][b] * 2);
      }
    }
}

So far I've been looking for different options for creating 2D arrays, but to no luck. I'm guessing because Haskell does not use mutable state so it's not a super popular option. It's probably just my java brain, but I'd love some people with functional background to perhaps give me a few pointers on how to go about thinking or solving for this conversion?

Answer 1

Usually doing mutation manually is a mistake an Haskell. It's awkward, and it reintroduces all the mutation bugs you normally don't get in Haskell. Usually you let laziness take care of things for you. Dynamic programming problems have a structure that's very straightforward to express with laziness in Haskell, but you need to start with a less obfuscated specification of the code.

The first thing to do is deobfuscate into an inefficient recursive representation. This was a complete pain for your example - I hope you were just typing code in more or less at random.

Here's what I got, expressed in Haskell, though I don't guarantee it to be correct:

present :: Int -> Int -> Int
present 0 0 = 1
present _ 0 = 0
present 0 b = negate (present 0 (b - 1))
present a b = future a b + 2 * present a (b - 1)

future :: Int -> Int -> Int
future 1 b = 2 * present 0 b
future a b = 3 * present (a - 1) (b - 1)

To get around your mutation, I had to use mutually recursive functions, with present conceptually tracking the state of the present row in your loop, and future tracking the state of the next row. Note that the future case for rows after the first doesn't exactly mirror what you wrote. I took the liberty of trimming out the dynamic[a+1][b+1] + part, as dynamic[a+1][b+1] is always going to be zero with the way your logic is laid out.

Normally you start dynamic programming with the recursive solution, so you don't need to go about reverse engineering like I did here. Also, you usually have something that doesn't look like completely random operations. I kind of like that there's mutual recursion between multiple functions, though. It makes the next part cooler.

Let's investigate a bit in ghci, just to get a rough idea how it performs.

*Main> :set +s
*Main> present 10 10
-39366
(0.00 secs, 801,616 bytes)
*Main> present 11 11
-118098
(0.00 secs, 1,530,632 bytes)
*Main> present 20 20
-2324522934
(1.07 secs, 746,657,288 bytes)
*Main> present 21 21
-6973568802
(2.22 secs, 1,493,244,064 bytes)
*Main> present 22 22
-20920706406
(4.14 secs, 2,986,417,752 bytes)

That's starting to look roughly like the expected exponential growth in runtime.

Here's where things get cool. Values in Haskell can be defined in terms of themselves. The basic idea is to set up regular boxed arrays corresponding to each function, where the value of each cell is expressed via a function that replaces function calls with an array lookup. As long as there isn't any circularity in the definition, laziness just makes it all work.

Here's what it looks like, in code:

import Data.Array
import Data.Ix

memoPresent :: Int -> Int -> Int
memoPresent r c = pArray ! (r, c)
  where
    bounds = ((0, 0), (r, c))

    pArray = listArray bounds (map (uncurry present) (range bounds))

    present 0 0 = 1
    present _ 0 = 0
    present 0 b = negate (pArray ! (0, b - 1))
    present a b = fArray ! (a, b) + 2 * pArray ! (a, b - 1)

    fArray = listArray bounds (map (uncurry future) (range bounds))

    future 1 b = 2 * pArray ! (0, b)
    future a b = 3 * pArray ! (a - 1, b - 1)

If you're paying close attention, you might notice that the whole first row of fArray isn't defined. You'd get a error if anything from that row was accessed, but that's the same situation you end up in with the recursive code, if you called future 0 whatever.

Let's see how this performs:

*Main> :set +s
*Main> memoPresent 10 10
-39366
(0.00 secs, 194,176 bytes)
*Main> memoPresent 11 11
-118098
(0.00 secs, 223,344 bytes)
*Main> memoPresent 20 20
-2324522934
(0.00 secs, 521,944 bytes)
*Main> memoPresent 21 21
-6973568802
(0.00 secs, 566,544 bytes)
*Main> memoPresent 22 22
-20920706406
(0.00 secs, 616,304 bytes)
*Main> memoPresent 100 100
1989748563691696842
(0.01 secs, 10,442,400 bytes)
*Main> memoPresent 200 200
7879235843265279210
(0.05 secs, 41,116,704 bytes)
*Main> memoPresent 1000 1000
-4135538464527847958
(1.26 secs, 1,064,652,488 bytes)

Huh. I didn't expect it would suddenly start getting positive answers. Oh, that's probably just Int underflow. Integer might have been a better choice of type, though it wouldn't reflect your Java code as well.

Anyway - the translation from recursive form to dynamic programming is really straightforward in Haskell if you use laziness to your advantage. You just need to make sure you do your original formulation in terms of the inefficient recursion instead of obfuscated but efficient looping mutation.

Answer 2

Dynamic programming usually relies on mutability for efficiency. But that's totally doable in Haskell. The array and vector packages both provide mutable array data structures. The APIs are slightly different than what you are probably used to in Java, but usually algorithms such as yours have a pretty direct translation. For example, here's your algorithm using the array package and the ST monad:

import Control.Monad
import Control.Monad.ST
import Data.Array.Unboxed
import Data.Array.MArray.Safe
import Data.Array.ST.Safe

foo :: Int -> UArray (Int,Int) Int
foo size = runSTUArray $ do
  dynamic <- newArray ((0,size-1),(0,size-1)) 0
  writeArray dynamic (0,0) 1
  forM_ [0..size-1] $ \a -> do
    forM_ [a..size-1] $ \b -> do
      v <- readArray dynamic (a,b)
      if a == 0 then do
        writeArray dynamic (a+1,b+1) (v*2)
        writeArray dynamic (a, b+1) (v*(-1))
      else do
        v1 <- readArray dynamic (a+1,b+1)
        writeArray dynamic (a+1,b+1) (v1 + v * 3)
        v2 <- readArray dynamic (a,b+1)
        writeArray dynamic (a,b+1) (v2 + v * 2)
  return dynamic