如何在没有强制的情况下将列表展平为列表? [英] How to flatten a list to a list without coercion?

问题描述

我正在尝试实现类似于 unlist 的功能，但类型不会被强制转换为向量，而是返回具有保留类型的列表.例如:

I am trying to achieve the functionality similar to unlist, with the exception that types are not coerced to a vector, but the list with preserved types is returned instead. For instance:

flatten(list(NA, list("TRUE", list(FALSE), 0L))

应该返回

list(NA, "TRUE", FALSE, 0L)

代替

c(NA, "TRUE", "FALSE", "0")

由 unlist(list(list(NA, list("TRUE", list(FALSE), 0L)) 返回.

从上面的例子可以看出，扁平化应该是递归的.标准 R 库中是否有一个函数可以实现这一点，或者至少有一些其他函数可以用来轻松有效地实现这一点?

As it is seen from the example above, the flattening should be recursive. Is there a function in standard R library which achieves this, or at least some other function which can be used to easily and efficiently implement this?

UPDATE:不知道上面的有没有说清楚，但是非列表不应该被扁平化，即flatten(list(1:3, list(4,5))) 应该返回 list(c(1, 2, 3), 4, 5).

UPDATE: I don't know if it is clear from the above, but non-lists should not be flattened, i.e. flatten(list(1:3, list(4, 5))) should return list(c(1, 2, 3), 4, 5).

推荐答案

有趣的非平凡问题！

主要更新 发生了这一切之后，我重新编写了答案并删除了一些死胡同.我还对不同情况的各种解决方案进行了计时.

MAJOR UPDATE With all that's happened, I've rewrote the answer and removed some dead ends. I also timed the various solutions on different cases.

这是第一个，相当简单但速度较慢的解决方案:

Here's the first, rather simple but slow, solution:

flatten1 <- function(x) {
  y <- list()
  rapply(x, function(x) y <<- c(y,x))
  y
}

rapply 允许您遍历列表并对每个叶元素应用一个函数.不幸的是，它与返回值的 unlist 完全一样.所以我忽略了 rapply 的结果，而是通过执行 <<- 将值附加到变量 y.

rapply lets you traverse a list and apply a function on each leaf element. Unfortunately, it works exactly as unlist with the returned values. So I ignore the result from rapply and instead I append values to the variable y by doing <<-.

以这种方式增长 y 不是很有效(它在时间上是二次的).因此，如果有数千个元素，这将非常慢.

Growing y in this manner is not very efficient (it's quadratic in time). So if there are many thousands of elements this will be very slow.

一种更有效的方法如下，来自@JoshuaUlrich 的简化:

A more efficient approach is the following, with simplifications from @JoshuaUlrich:

flatten2 <- function(x) {
  len <- sum(rapply(x, function(x) 1L))
  y <- vector('list', len)
  i <- 0L
  rapply(x, function(x) { i <<- i+1L; y[[i]] <<- x })
  y
}

这里我先找出结果长度并预先分配向量.然后我填写值.如您所见，此解决方案要快得多.

Here I first find out the result length and pre-allocate the vector. Then I fill in the values. As you can will see, this solution is much faster.

这是基于 Reduce 的@JoshO'Brien 出色解决方案的一个版本，但经过扩展后可以处理任意深度:

Here's a version of @JoshO'Brien great solution based on Reduce, but extended so it handles arbitrary depth:

flatten3 <- function(x) {
  repeat {
    if(!any(vapply(x, is.list, logical(1)))) return(x)
    x <- Reduce(c, x)
  }
}

现在开始战斗吧！

# Check correctness on original problem 
x <- list(NA, list("TRUE", list(FALSE), 0L))
dput( flatten1(x) )
#list(NA, "TRUE", FALSE, 0L)
dput( flatten2(x) )
#list(NA, "TRUE", FALSE, 0L)
dput( flatten3(x) )
#list(NA_character_, "TRUE", FALSE, 0L)

# Time on a huge flat list
x <- as.list(1:1e5)
#system.time( flatten1(x) )  # Long time
system.time( flatten2(x) )  # 0.39 secs
system.time( flatten3(x) )  # 0.04 secs

# Time on a huge deep list
x <-'leaf'; for(i in 1:11) { x <- list(left=x, right=x, value=i) }
#system.time( flatten1(x) ) # Long time
system.time( flatten2(x) )  # 0.05 secs
system.time( flatten3(x) )  # 1.28 secs

...所以我们观察到的是，Reduce 解决方案在深度低时更快，而 rapply 解决方案在深度大时更快！

...So what we observe is that the Reduce solution is faster when the depth is low, and the rapply solution is faster when the depth is large!

随着正确性的发展，这里有一些测试:

As correctness goes, here are some tests:

> dput(flatten1( list(1:3, list(1:3, 'foo')) ))
list(1L, 2L, 3L, 1L, 2L, 3L, "foo")
> dput(flatten2( list(1:3, list(1:3, 'foo')) ))
list(1:3, 1:3, "foo")
> dput(flatten3( list(1:3, list(1:3, 'foo')) ))
list(1L, 2L, 3L, 1:3, "foo")

不清楚想要什么结果，但我倾向于 flatten2...

Unclear what result is desired, but I lean towards the result from flatten2...

这篇关于如何在没有强制的情况下将列表展平为列表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！