Efficient way to remove empty lists from lists without evaluating expressions?

Question

The previous thread suggested an efficient way to remove empty lists ( {} ) from lists:

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

Using the in-place Trott-Strzebonski evaluation method , this method can be generalized to work with held expressions:

 f1[expr_] := Replace[expr, x_List :> With[{eval = DeleteCases[x, {}]}, eval /; True], {0, Infinity}] 

This solution is more efficient than the ReplaceRepeated based ReplaceRepeated :

 f2[expr_] := expr //. {left___, {}, right___} :> {left, right} 

But it has one drawback: it evaluates held expressions if they are wrapped in a List :

 In[20]:= f1[Hold[{{}, 1 + 1}]] Out[20]= Hold[{2}] 

So my question is: what is the most efficient way to remove all empty lists ( {} ) from lists without evaluating expressions? An empty List[] object should only be deleted if it is an element of another List .

---

Here are some timings:

 In[76]:= expr = Tuples[Tuples[{{}, {}}, 3], 4]; First@Timing [#[expr]] & /@ {f1, f2, f3} pl = Plot3D[Sin[xy], {x, 0, Pi}, {y, 0, Pi}]; First@Timing [#[pl]] & /@ {f1, f2, f3} Out[77]= {0.581, 0.901, 5.027} Out[78]= {0.12, 0.21, 0.18} 

Definitions:

 Clear[f1, f2, f3]; f3[expr_] := FixedPoint[ Function[e, Replace[e, {a___, {}, b___} :> {a, b}, {0, Infinity}]], expr]; f1[expr_] := Replace[expr, x_List :> With[{eval = DeleteCases[x, {}]}, eval /; True], {0, Infinity}]; f2[expr_] := expr //. {left___, {}, right___} :> {left, right}; 

Answer 1

What about:

 Clear[f3]; f3[expr_] := FixedPoint[ Function[e, Replace[e, {a___, {}, b___} :> {a, b}, {0, Infinity}]], expr] 

This seems to fit the specifications:

 In[275]:= f3[{a, {}, {b, {}}, c[d, {}]}] Out[275]= {a, {b}, c[d, {}]} In[276]:= f3[Hold[{{}, 1 + 1, {}}]] Out[276]= Hold[{1 + 1}] 

Answer 2

You can combine the solutions you mentioned with minimal performance gains and maintain code that has not been evaluated using the technique in this post with the modification that the user holding wrapper will be closed using Module :

 ClearAll[removeEmptyListsHeld]; removeEmptyListsHeld[expr_Hold] := Module[{myHold}, SetAttributes[myHold, HoldAllComplete]; Replace[MapAll[myHold, expr, Heads -> True], x : myHold[List][___] :> With[{eval = DeleteCases[x, myHold[myHold[List][]]]}, eval /; True], {0, Infinity}]//. myHold[x_] :> x]; 

The above function assumes the input expression is wrapped in Hold . Examples:

 In[53]:= expr = Tuples[Tuples[{{}, {}}, 3], 4]; First@Timing [#[expr]] & /@ {f1, f2, f3, removeEmptyListsHeld[Hold[#]] &} Out[54]= {0.235, 0.218, 1.75, 0.328} In[56]:= removeEmptyListsHeld[Hold[{{},1+1,{}}]] Out[56]= Hold[{1+1}] 

Answer 3

I'm a little late with this .; -)

Although this is a rather complicated test, an order of magnitude faster than your f1 :

 fx[expr_] := Module[{s}, expr // Quiet[{s} /. {x_} :> ({} /. {x___} -> (# /. {} -> x //. {x ..} -> x) &)] ] 

He does not evaluate:

 Hold[{{}, 1 + 1}] // fx 

 Hold[{1 + 1}] 

Delays

 expr = Tuples[Tuples[{{}, {}}, 3], 4]; First @ Timing @ Do[# @ expr, {100}] & /@ {f1, fx} pl = Plot3D[Sin[xy], {x, 0, Pi}, {y, 0, Pi}]; First @ Timing @ Do[# @ pl, {100}] & /@ {f1, fx} 

 {10.577, 0.982} (* 10.8x faster *) {1.778, 0.266} (* 6.7x faster *) 

Verify

 f1@expr === fx@expr f1@pl === fx@pl 

 True True 

Explanation

The basic version of this function will look like this:

 {} /. {x___} -> (# //. {} | {x ..} -> x) & 

The idea is to first reduce the expression with //. {} | {x ..} -> x //. {} | {x ..} -> x //. {} | {x ..} -> x , and then use the injector pattern with an empty expression to remove all instances of x , as if they were replaced by Sequence[] , but without evaluation.

The first change is to optimize a bit by dividing the replacement by /. {} -> x //. {x ..} -> x /. {} -> x //. {x ..} -> x /. {} -> x //. {x ..} -> x . The second change is to somehow localize x in the templates so that it does not fail if x appears in the expression itself. Due to the way Mathematica handles nested outline structures, I cannot just use Module[{x}, . . . ] Module[{x}, . . . ] Module[{x}, . . . ] , but instead you need to use the injector pattern again to get a unique character in x___ , etc. And Quiet , so that he does not complain about non-standard use.