From a tree, recursively pluck all elements with a particular name

pluck_recursive.R

# @drob's version from https://twitter.com/drob/status/1501747414780239879
pluck_recursive <- function(lst, name) {
  if (is.list(lst)) {
    if (!is.null(lst[[name]])) {
      return(lst[[name]])
    }
    return(unname(unlist(purrr::map(lst, pluck_recursive, name))))
  }
}

# @winston_chang's version
# A fast version of pluck_recursive. This simply walks the tree, and whenever it
# finds an item that matches, it adds that item to a list.
# This function uses a few tricks to speed things up:
# - Instead of lapply() or map(), it uses a for loop, so that it doesn't have to
#   allocate a new list each time it recurses.
# - The results are accumulated in a variable `result`, which is captured in the
#   inner function's scope. Instead of building lists at each level of recursion
#   and joining them together, we just have a single list that we modify.
# - When appending to `result`, assign past the end with `<<-`. This avoids
#   creating a copy of the list each time an item is added; R modifies the list
#   in place.
pluck_recursive2 <- function(x, name) {
  result <- list()
  
  pluck_r <- function(x, name) {
    x_names <- names(x)
    # Need to watch out for unnamed lists
    is_named_list <- !is.null(x_names)

    for(i in seq_along(x)) {
      if (is_named_list && x_names[i] == name) {
        result[[length(result) + 1]] <<- x[[i]]
      } else if (is.list(x[[i]])) {
        pluck_r(x[[i]], name)
      }
    }
  }
  
  pluck_r(x, name)
  
  result
}


x <- list(list(
  a=list(b=2, repeated=3),
  c=list(list(d=4, e=list(repeated=5,f=6)))
))


microbenchmark::microbenchmark(
  pluck_recursive(x, "target"),
  pluck_recursive2(x, "target")
)
#> Unit: microseconds
#>                           expr    min    lq     mean median      uq    max neval
#>   pluck_recursive(x, "target") 32.595 33.21 34.91929 33.497 33.9275 84.214   100
#>  pluck_recursive2(x, "target")  5.166  5.33  5.68670  5.453  5.6580 15.170   100