2

After you get a basic idea, coding dynamic programming (DP) problems in imperative style is pretty straightforward, at least for simpler DP problems. It usually involves some form of table, that we iteratively fill based on some formula. This is pretty much all there is for implementing bottom-up DP.

Let's take Longest Increasing Subsequence (LIS) as a simple and common example of a problem that can be solved with bottom-up DP algorithm.

C++ implementation is straightforward (not tested):

// Where A is input (std::vector<int> of size n)
std::vector<int> DP(n, 0);
for(int i = 0; i < n; i++) {
    DP[i] = 1;
    for(int j = 0; j < i; j++) {
        if (A[i] > A[j]) {
            DP[i] = std::max(DP[i], DP[j] + 1);
        }
    }
}

We've just described "how to fill DP" which is exactly what imperative programming is.

If we decide to describe "what DP is", which is kind of a more FP way to think about it, it gets a bit more complicated. Here's an example Scala code for this problem:

// Where A is input
val DP = A.zipWithIndex.foldLeft(Seq[Int]()) {
    case (_, (_, 0)) => Seq(1)
    case (d, (a, _)) =>
      d :+ d.zipWithIndex.map { case (dj, j) =>
        dj + (if (a > A(j)) 1 else 0)
      }.max
}

To be quite honest, this Scala implementation doesn't seem that much idiomatic. It's just a translation of imperative solution, with immutability added to it.

I'm curious, what is a general FP way to deal with things like this?

Nikola Ninkovic
  • 1,252
  • 1
  • 12
  • 27
  • 1
    I don't know about scala, but a lot of functional programming libraries have a `memoize` pattern that does caching in a transparent manner. – Willem Van Onsem Jul 23 '17 at 18:09
  • Yeah, thanks for pointing me in that direction, will look it up to find out more. Still, at glance, it seems like it's more applicable to top-down DP algorithms? Thanks! – Nikola Ninkovic Jul 23 '17 at 18:43
  • Thanks for that, but I was looking for more general approach. – Nikola Ninkovic Jul 23 '17 at 19:02
  • The basic idea is to represent `DP` as a stream and declare a recursive function that generates it. You can inspire from a bit more simple problem of generating Fibonacci numbers https://stackoverflow.com/questions/9864497/generate-a-sequence-of-fibonacci-number-in-scala . – simpadjo Jul 23 '17 at 19:35
  • I'm sorry, but I don't think that has anything to do with DP. I don't think that the solution on the link you've provided does any memoization at all. – Nikola Ninkovic Jul 24 '17 at 01:18

1 Answers1

3

I don't know much about DP but I have a few observations that I hope will contribute to the conversation.

First, your example Scala code doesn't appear to solve the LIS problem. I plugged in the Van der Corput sequence as found on the Wikipedia page and did not get the designated result.

Working through the problem this is the solution I came up with.

def lis(a: Seq[Int], acc: Seq[Int] = Seq.empty[Int]): Int =
  if      (a.isEmpty)         acc.length
  else if (acc.isEmpty)       lis(a.tail, Seq(a.head))   max lis(a.tail)
  else if (a.head > acc.last) lis(a.tail, acc :+ a.head) max lis(a.tail, acc)
  else                        lis(a.tail, acc)

lis(Seq(0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15)) // res0: Int = 6

This can be adjusted to return the subsequence itself, and I'm sure it can be tweaked for better performance.

As for memoization, it's not hard to roll-your-own on an as-needed basis. Here's the basic outline to memoize any arity-2 function.

def memo[A,B,R](f: (A,B)=>R): ((A,B)=>R) = {
  val cache = new collection.mutable.WeakHashMap[(A,B),R]
  (a:A,b:B) => cache.getOrElseUpdate((a,b),f(a,b))
}

With this I can create a memoized version of some often called method/function.

val myfunc = memo{(s:String, i:Int) => s.length > i}
myfunc("bsxxlakjs",7)  // res0: Boolean = true

Note: It used to be that WeakHashMap was recommended so that the cache could drop lesser used elements in memory-challenged environments. I don't know if that's still the case.

jwvh
  • 50,871
  • 7
  • 38
  • 64