Objective

This question is related to, but is not covered or answered by 73083349, 63074814, 76103332, 70272176, 59820309, 74276459.

I’m trying to find/create an efficient (read: fast) function in R that will return a character vector containing all of the relative paths of all fields or, optionally, those fields that satisfy a specified predicate function, at all depths of a nested list or data.frame of arbitrary depth.

Example

To illustrate, say I have the following data structure (a data.table in this instance, but it could just as well have been a tibble or a “normal” list):

input <- data.table(
  a = c(1, 2, 3, 4),
  b = LETTERS[1:4],
  c = list(
    list(a = 1, g = 2),
    list(a = 1),
    list(a = 1, b = 50),
    list(a = 1, zeta = data.frame(one = 'two', two = 'three'))
  ),
  d = list(
    data.frame(
      x = c(1, 2),
      y = LETTERS[1:2],
      z = data.frame(a = c("10", "20"))
    ),
    data.frame(
      x = c(3, 4, 5),
      y = LETTERS[3:5],
      z = data.frame(a = c("30", "40", "50"))
    ),
    data.frame(
      x = 6,
      y = LETTERS[6],
      z = 'another_thing',
      zz = list(a = "60", p = 'eish')
    ),
    data.frame(
      x = 7:12,
      y = LETTERS[7:12],
      z = data.frame(a = as.character(70:75))
    )
  )
)

The desired output (and, crucially, the desired output format) of the base version of the function when applied to input would then look as follows:

c(
  "[['a']]",
  "[['b']]",
  "[['c']]",
  "[['c']][[1]]",
  "[['c']][[1]][['a']]",
  "[['c']][[1]][['g']]",
  "[['c']][[2]]",
  "[['c']][[2]][['a']]",
  "[['c']][[3]]",
  "[['c']][[3]][['a']]",
  "[['c']][[3]][['b']]",
  "[['c']][[4]]",
  "[['c']][[4]][['a']]",
  "[['c']][[4]][['zeta']]",
  "[['c']][[4]][['zeta']][['one']]",
  "[['c']][[4]][['zeta']][['two']]",
  "[['d']]",
  "[['d']][[1]]",
  "[['d']][[1]][['x']]",
  "[['d']][[1]][['y']]",
  "[['d']][[1]][['a']]",
  "[['d']][[2]]",
  "[['d']][[2]][['x']]",
  "[['d']][[2]][['y']]",
  "[['d']][[2]][['a']]",
  "[['d']][[3]]",
  "[['d']][[3]][['x']]",
  "[['d']][[3]][['y']]",
  "[['d']][[3]][['z']]",
  "[['d']][[3]][['zz.a']]",
  "[['d']][[3]][['zz.p']]",
  "[['d']][[4]]",
  "[['d']][[4]][['x']]",
  "[['d']][[4]][['y']]",
  "[['d']][[4]][['a']]"
)

In other words, the output provides an exhaustive list of the paths of all fields, at all depths relative to the root input object.

Current approach

I have created the find_paths recursive function below. The function accepts the following arguments:

• .x: The root nested list or data.frame to search
• .p: An (optional) predicate function to apply to determine if a particular field path should be added to the output.
• max_depth: The maximum nesting depth to “search” for elements (this is useful to limit the depth of initial “searches”).
• current_path, current_depth, and paths: Arguments the are updated internally with recursion.

find_paths <- function(.x,
                       .p = NULL,
                       max_depth = Inf,
                       current_path = '',
                       current_depth = 0,
                       paths = NULL) {
  # stop searching once max_depth has been reached
  if (current_depth > max_depth) return(paths)
  
  # apply predicate function if specified
  if (is.function(.p)) {
    if (current_depth > 0 & .p(.x)) {
      paths <- c(paths, current_path)
    }
  } else {
    if (current_depth > 0) {
      paths <- c(paths, current_path)
    }
  }
  
  # recursive part: check list-iness and continue building path
  if (is.list(.x)) {
    if (is.null(names(.x))) {
      for (i in seq_along(.x)) {
        new_path <- paste0(current_path, "[[", i, "]]")
        paths <- find_paths(
          .x = .x[[i]],
          .p = .p,
          max_depth = max_depth,
          current_path = new_path,
          current_depth = current_depth + 1,
          paths = paths
        )
      }
    } else {
      for (name in names(.x)) {
        new_path <- paste0(current_path, "[['", name, "']]")
        paths <- find_paths(
          .x = .x[[name]],
          .p = .p,
          max_depth = max_depth,
          current_path = new_path,
          current_depth = current_depth + 1,
          paths = paths
        )
      }
    }
  }
  
  # return paths
  paths
}


# usage without predicate (produces output as shown above)
find_paths(.x = input)

# usage with predicate (returns only character element paths)
find_paths(.x = input, .p = is.character)

This function works correctly in the sense that it produces the desired output when applied to objects like input. However, it is prohibitively slow (I realise this is very much a subjective judgment) when applied to larger or more complex nested structures than input. The data on which I’d like/need to apply this function often has many hundreds of thousands of rows with hundreds of deeply – e.g. up to 8 levels deep – nested fields. My questions are:

1. Am I missing something obvious? Is this kind of task slow by its very nature? Is recursion even the correct way to go here? I suspect that recursion is going to be unavoidable if one wants to apply a predicate function, but I’d have thought (read: hoped) that there would be a simpler way to just return all of the names/addresses/paths (not even sure what the right terminology is) for nested objects in R.
2. Does anyone know of a better (i.e. faster) alternative approach to this one? I’ve experimented a fair bit with other approaches (e.g. those mentioned in the posts linked at the top of this question), but most of these (e.g. unlisting the root nested object) entail transformations of the input object that are so computationally expensive that they effectively negate any potential advantages of avoiding recursion.