Как вы memoise с делами в Scala?

Question

Каков наилучший способ преобразования этого кода, который использует memoization в правильную Scala, используя случаи и функциональное программирование?

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) 
} 

Answer 1

Это модифицированная версия кода, который использует match и 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) 
} 

Это не так легко преобразовать этот код в чистой функциональной версии, из-за состояния, сохраненного в seen массиве , Но это состояние может быть скрыто для остальной части приложения, используя функцию декоратор:

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