How do you memoization with cases in Scala?

Question

What is the best way to convert this code which uses memoization into proper Scala using cases and functional programming?

def uniquePathsMemoization(n:Int, m:Int, row:Int, col:Int, seen:Array[Array[Int]]):Int = {
  if (row == m && col == n) 1
  if (row > m || col > n) 0

  if (seen(row+1)(col) == -1) seen(row+1)(col) = uniquePathsMemoization(n, m, row + 1, col, seen)
  if (seen(row)(col + 1) == -1 ) seen(row)(col) = uniquePathsMemoization(n,m, row, col + 1, seen)

seen(row+1)(col) + seen(row)(col + 1)
}

Check out this question http://stackoverflow.com/questions/25129721/scala-memoization-how-does-this-scala-memo-work — Rikard, Jan 17 '15 at 21:20

Alvaro González Sotillo · Accepted Answer · 2015-01-19T09:59:52.437

This is a modified version of your code that uses match and case

def uniquePathsMemoization(n:Int, m:Int, row:Int, col:Int, seen:Array[Array[Int]]):Int = (row,col) match{

  case (row,col) if row == m && col == n =>
    1
  case (row,col) if row > m || col > n =>
    0
  case (row,col) =>
    if (seen(row+1)(col) == -1) seen(row+1)(col) = uniquePathsMemoization(n, m, row + 1, col, seen)
    if (seen(row)(col + 1) == -1 ) seen(row)(col) = uniquePathsMemoization(n,m, row, col + 1, seen)

    seen(row+1)(col) + seen(row)(col + 1)
}

It is not easy to convert this code to a pure functional version, due to the state stored in the seen array. But this state can be hidden for the rest of the application, using a function decorator:

def uniquePathsMemoizationGenerator( maxRows: Int, maxCols:Int ) : (Int,Int,Int,Int) => Int = {


  def uniquePathsMemoization(n:Int, m:Int, row:Int, col:Int, seen:Array[Array[Int]]):Int = (row,col) match{

    case (row,col) if row == m && col == n =>
      1
    case (row,col) if row > m || col > n =>
      0
    case (row,col) =>
      if (seen(row+1)(col) == -1) seen(row+1)(col) = uniquePathsMemoization(n, m, row + 1, col, seen)
      if (seen(row)(col + 1) == -1 ) seen(row)(col) = uniquePathsMemoization(n,m, row, col + 1, seen)

      seen(row+1)(col) + seen(row)(col + 1)
  }

  val seen = Array.fill(maxRows,maxCols)(-1)
  uniquePathsMemoization(_,_,_,_,seen)
}

val maxRows = ???
val maxCols = ???
val uniquePaths = uniquePathsMemoizationGenerator( maxRows, maxCols )

// Use uniquePaths from this point, instead of uniquePathsMemoization

How do you memoization with cases in Scala?

1 Answers1