How to clear the 'memo' or better understand scoping in R with memoised recursive functions using superassignment "<<-"

Question

I was following along with a dynamic programming tutorial and trying to adapt their code for R. A solution I see in lots of posts for memoization in R starts by creating a local environment in which the memo object is created. That memo object doesn't get 'cleared' between calls to the function. For some common uses I could see how that would actually be a benefit-- if the calculations you're asking the function to make are basically 'fixed', then why do them multiple times in a session? But for this instance, it's a problem.

This recursive function takes a target integer and a list of integers, and returns 'TRUE' if any combination of the list (with replacement) can sum to the target, otherwise 'FALSE'.

cS <- function(targetSum, numbers){

  if(targetSum < 0){ return(FALSE) }
  if(targetSum == 0){ return(TRUE) }
  remainder <- list()

  for(i in 1:length(numbers)){
    remainder[i] = targetSum - numbers[i]
    if(cS(remainder[[i]], numbers) == TRUE){ return(TRUE) }
  }

  return(FALSE)

}

cS(7, c(2,3)) # TRUE
cS(7, c(5,3,4,7)) # TRUE
cS(7, c(2,4)) # FALSE

And my attempt to memoise it:

cSm <- local({

  key <- list()

  function(targetSum, numbers){

    valueName <- as.character(targetSum)
    if(!is.null(key[[valueName]])){ return(key[[valueName]]) }
    if(targetSum < 0){ return(FALSE) }
    if(targetSum == 0){ return(TRUE) }

    remainder <- list()
    for(i in 1:length(numbers)){
      remainder[i] = targetSum - numbers[i]
      # browser()
      if(Recall(remainder[[i]], numbers) == TRUE){ 
        valueName <- as.character(remainder[[i]])
        key[[valueName]] <<- TRUE
        return(TRUE)
      } 
    }

    key[[valueName]] <<- FALSE
    # print(key)
    return(FALSE)

  }
})

cSm(7, c(2,3)) # TRUE
cSm(7, c(5,3,4,7)) # TRUE
cSm(7, c(2,4)) # expected FALSE, returns TRUE

>get("key", environment(cSm)) # there are 'leftovers' from prior calls

$`1`
[1] FALSE

$`0`
[1] TRUE

$`3`
[1] TRUE

$`5`
[1] TRUE

$`2`
[1] FALSE

$`4`
[1] TRUE

Why doesn't key <- list() on the first line within local() wipe the slate clean each time the function is called? If I make key <- NULL in the environment of the function between each call to cSm, it works as expected, but I'd like to do better.

>assign("key", NULL, envir = environment(cSm))
>get("key", envir = environment(cSm))

NULL

>cSm(7, c(2,4)) # FALSE

[1] FALSE

>get("key", envir = environment(cSm))

$`1`
[1] FALSE

$`3`
[1] FALSE

$`5`
[1] FALSE

$`7`
[1] FALSE

Is there an easy solution I don't see? Should I try to avoid using <<- ? What are my options?

Answer 1

Try running the recursion within csm:

cSm <- function(targetSum, numbers){
  
  key <- list()
  
  recurser <- function(targetSum,numbers) {
    
    valueName <- as.character(targetSum)
    if(!is.null(key[[valueName]])){ return(key[[valueName]]) }
    if(targetSum < 0){ return(FALSE) }
    if(targetSum == 0){ return(TRUE) }
    
    remainder <- list()
    for(i in 1:length(numbers)){
      remainder[i] = targetSum - numbers[i]
      # browser()
      if(Recall(remainder[[i]], numbers) == TRUE){ 
        valueName <- as.character(remainder[[i]])
        key[[valueName]] <<- TRUE
        return(TRUE)
      } 
    }
    
    key[[valueName]] <<- FALSE
    # print(key)
    return(FALSE)
    
  }
  
  
  recurser(targetSum, numbers)
}



cSm(7, c(2,3)) # TRUE
cSm(7, c(5,3,4,7)) # TRUE
cSm(7, c(2,4)) # FALSE