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

### 问题描述

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))` 返回.

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 `<<-`.

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.

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.

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")
``````

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