<img height="1" width="1" src="https://www.facebook.com/tr?id=1076094119157733&amp;ev=PageView &amp;noscript=1">

Solving Dynamic Programming problems using Functional Programming (Part 2)

Posted by Miguel Vilá on Wed, Oct 4, 2017

In the last post we saw an imperative solution to the knapsack problem. In this post we will see an initial approach for doing the same thing functionally.

Translating every mutation to a state modification

In functional programming one way to handle state is the State monad. Then we could mindlessly replace the modifications by creating State values that represent those modifications. Using the State monad implementation in Cats and an immutable data structure like Vector we can reimplement the dp-fp-OnW.gif  space version like this:

First some imports:

import cats._, cats.instances.all._, cats.syntax.traverse._, cats.syntax.foldable._
import cats.data.State

This function will prove useful when updating the state:

def setSolution(i: Int, j: Int, newVal: Int)
               (solutions: Vector[Vector[Int]]): Vector[Vector[Int]] =
    solutions.updated(i, solutions(i).updated(j, newVal))

and the whole thing:

def knapsack(maxWeight: Int, value: Vector[Int], weight: Vector[Int]): Int = {
    val n = value.length
    val initialState: Vector[Vector[Int]] = Vector.fill(n+1, maxWeight + 1)( 0 )
    val st: State[Vector[Vector[Int]], Unit] = ( 1 to n ).toList.traverseU_ { i =>
        ( 1 to maxWeight ).toList.traverseU_ { j =>
            for {
                solutions <- State.get[Vector[Vector[Int]]]
                newVal = if( j - weight(i-1) >= 0 ) {
                    Math.max(
                        solutions(i-1)(j) , 
                        solutions(i-1)(j - weight(i-1)) + value(i-1) 
                    )
                } else {
                    solutions(i-1)(j)
                }
                _ <- State.modify(setSolution(i,j,newVal))
            } yield ()
        }
    }
    val solution = st.runS(initialState).value
    solution(n)(maxWeight)
}

Not too interesting. This even looks too much like the original code. In a similar way we can do the same for the dp-fp-OW.gif space version:

def knapsack(maxWeight: Int, value: Vector[Int], weight: Vector[Int]): Int = {
    val n = value.length
    val initialState: Vector[Int] = Vector.fill(maxWeight + 1)( 0 )
    val st: State[Vector[Int], Unit] = ( 1 to n ).toList.traverseU_ { i =>
        for {
            solutions <- State.get[Vector[Int]]
            newSolutions = 0 +: ( 1 to maxWeight ).map { j: Int =>
                if( j - weight(i-1) >= 0 ) {
                    Math.max(
                        solutions(j) , 
                        solutions(j - weight(i-1)) + value(i-1) 
                    )
                } else {
                    solutions(j)
                }
            }.toVector
            _ <- State.set(newSolutions)
        } yield ()
    }
    val solution = st.runS(initialState).value
    solution(maxWeight)
}

 Have we learned anything from this? Not much, really. And this is boring precisely because the state monad can be used to implement the very same imperative logic. This solves the problem in a functional way but it’s kind of an over-engineered approach. Is there a simpler, more elegant and functional way to do this?

Just use fold!

In the imperative version at each iteration we are computing a new row based on the last one. And we are interested in the last row because it holds the final answer. The first row is full of zeros, that's our "base case". And a perfect function for building incremental state from an initial state is `fold`! `fold` has two parameters: the initial state and a function that computes a new state based on the previous one and on the current element of the structure we are folding over. This fits us perfectly because to compute each new row we must have two ingredients: the previous row and which row number is that we are processing. We could start by folding over a list of the row numbers starting with a row full of zeros:

val firstRow = Vector.fill(maxWeight + 1)( 0 )
val lastRow = (1 to n).foldLeft(firstRow) { (upperRow, i) =>
    ??? // How to compute each new row?
}
val answer = lastRow.last

To compute the new row we must do the same that we were doing before. Well, kind of: instead of modifying the input we are going to return a new row. To do this we can compute each value based on the column number, the row number and the values of the previous row:

val firstRow = Vector.fill(maxWeight + 1)( 0 )
val lastRow = (1 to n).foldLeft(firstRow) { (upperRow, i) =>
    0 +: (1 to maxWeight).map { j => 
        if( j - weight(i-1) >= 0 ) {
            Math.max( 
                upperRow(j) ,
                upperRow(j - weight(i-1)) + value(i-1)
            )
        } else {
            upperRow(j)
        }
    }.toVector
}
val answer = lastRow.last

And that's pretty much it! There's no mutation and we accomplish the same thing with very similar code! This even has dp-fp-OW.gif  space complexity. 

What we have seen so far

In this post we saw two functional solutions to a dynamic programming problem. The first approach is very equivalent to the imperative solution and the second one uses a higher order function. In the next post we will see what happens when the dependencies between the solutions have another shape.

Posts by Topic

see all

Subscribe to Email Updates