Efficient way to remove empty lists from lists?

Question

What is the most efficient way to remove all empty List[] objects from all of the Lists that appear in an expression at different levels? The empty List[] should be removed only if it is an element of another List itself.

Answer 1

Andrew and Alexey point out that using expr //. x_List :> DeleteCases[x, {}, Infinity] as I had in my previous answer will also remove the {} in blah[{f[{}]}], whereas it should leave it untouched as its head is f, not a List. The solution, thanks to Leonid, is to not use ReplaceRepeated, but Replace instead with replacements being made at all levels from 0 through Infinity:

Replace[expr, x_List :> DeleteCases[x, {}], {0, Infinity}]

---

The reason why Replace works and ReplaceRepeated doesn't can be seen from this little example. Consider expr = {a, {}, {b, {}}, c[d, {}]}; in its TreeForm

Replace works by starting with the innermost expression(s) first, i.e., List[b,{}] and c[d,{}], and works upwards to the top node. At each level, checking the head is as simple as looking up to the node right above and see if it matches List. If it does, apply the rule and move up a level, else do nothing and move up a level. This results in a final tree:

ReplaceRepeated (//.), on the other hand, works by starting with the top most node and traversing down the tree. The previous solution starts by checking if the first node is a List and if it is, then DeleteCases is applied and it moves down the tree, ruthlessly replacing every {} it can find. Note that it does not check if the heads of the inner expressions also match List, because this traversal is done by DeleteCases, not ReplaceRepeated. When //. moves to subsequent lower nodes, there is nothing more to replace and it exits quickly. This is the tree that one gets with the previous solution:

Note that the {} inside c[d, {}] has also been removed. This is solely due to the fact that DeleteCases (with level specification {0,Infinity} moves down the tree. Indeed, if the first head had been something other than List, it would've skipped it and moved to the next level, of which only the {} in {b, {}} is a match. To demostrate with expr2 = f[a, {}, {b, {}}, c[d, {}]], we get

Note that in the current solution with Replace, we use DeleteCases with the default level specification, which is the first level only. It does not, therefore, check for and delete empty lists deeper than on the first level, which is exactly what we need here.

Although we used the first node to explain why it fails, the reasoning holds true for every node. Leonid explains these concepts in greater detail in his book