# Pattern to match a non-empty list of non-empty lists

Is there a pattern to match a list of lists, containing at least one list, with each list containing at least one element?

In the Mathematica documentation it says that the pattern

x:{___List}


will match a list of lists. This is true, but it also matches {}, which is a list of zero lists (or zero anything). To make sure there is at least one list in my list of lists I can remove one of the underscores to change BlankNullSequence to BlankSequence, i.e. switch to

x:{__List}


which no longer matches {}. It does, however, match {{}}. How can I also guarantee that each matched sublist is non-empty? Is this even possible, or should I be checking for it programmatically within the Module to which I'm passing arguments of this form?

-

If I am understanding you:

x : {{__} ..}


Make sure you understand BlankSequence and Pattern as well.

Here is a breakdown of the expression above. First let us view the FullForm which is as close to the way Mathematica sees it as possible:

FullForm[ x:{{__}..} ]

Pattern[x,
List[
Repeated[
List[
BlankSequence[]
]
]
]
]


This expanded form is useful to remove any ambiguity in Mathematica's parsing.

Therefore from the inside out we have (short form : long form : description):

__ : BlankSequence[] : one or more arguments with any head

{ } : List[ ] : inside the head List

.. : Repeated[ ] : one or more arguments matching the given pattern

{ } : List[ ] : inside the head List

x: : Pattern[x, ] : a unique expression that matches the given pattern, named x

Pay attention to this last point: naming the pattern changes the way it behaves, such that it represents a unique expression. Consider this superficially similar pattern:

x : {{a__} ..}


This will only match e.g. {{1, 2}, {1, 2}, {1, 2}} but not {{1, 2}, {3}, {4, 5, 6}} because by naming the first sequence 1, 2 all other sequences must be identical. Simply matching the pattern a__ independently is not enough.

-
Thanks, that appears to do the trick for all test cases I've come up with... Could you elaborate on this at all? Am I interpreting correctly that the outer braces simply hold the pattern, the inner ones represent a list, the two underscores say that list must have at least one element, and the two periods indicate that there must be at least one such non-empty list? – Michael Underwood Feb 3 '12 at 23:45
@Michael I added links to useful documentation. The outer brackets are certainly part of the pattern (named x). {__} stands for a list with one or more elements, and .. is short form of Repeated which means one or more of the preceding expression. Please read all four documentation pages that I link to above, then return with any further questions. – Mr.Wizard Feb 3 '12 at 23:49
@MichaelUnderwood I'd also suggest reading this question and its answer. – rcollyer Feb 4 '12 at 1:14
That's the one - +1. – Leonid Shifrin Feb 4 '12 at 9:26

If you want to stick to the same pattern as your original you can also set up a test for empty lists as follows...

notEmptyListQ[x_List] /; Length[Flatten[x]] == 0 := False
notEmptyListQ[x_List] := True


Here I test it with a function f.

f[x : {___List?notEmptyListQ}] := True
f[___] := False

In[17]:= f[{{1}, {}}]

Out[17]= False

In[18]:= f[{{1}, {2}}]

Out[18]= True


Empty lists of arbitrary depth are excluded.

In[19]:= f[{{1}, {{{}}}}]

Out[19]= False


Checks like this can make code more readable (at least for me) and in some cases lessen the workload of the pattern matcher (though not so much in this case).

Edit: in order to prevent f[{}] from returning true, you would also have to check the outer list x if you insist on using BlankNullSequence.

That is...

f[x: {___List?notEmptyListQ}]/;notEmptyListQ[x]:= True


This is but one of the many good arguments against using BlankNullSequence unless you really need it.

-
+1 for alternatives :-) – Mr.Wizard Feb 4 '12 at 1:57
Got to keep that answer to question ratio up :) – Andy Ross Feb 4 '12 at 2:15
We're slipping a little, some questions only have 2 or 3 answers, not the customary 5 - 10. :) – rcollyer Feb 4 '12 at 3:15