How to define a recursive pattern?

Question

I want to translate this recursive syntactic definition into a Mathematica pattern¹:

$$ \mathtt{x}: \begin{cases} \text{Null}\\ \{\textit{integer}, \mathtt{x}\} \end{cases} $$

In other words, all the following Mathematica expressions should match the desired pattern:

Null
{4, Null}
{3, {4, Null}}
{2, {3, {4, Null}}}
{1, {2, {3, {4, Null}}}}

...but none of these should

{}
{Null}
{Null, Null}
{3, 4, Null}

I thought that x:(Null|{_Integer, x}) would do the job, and at least

MatchQ[Null, x : (Null | {_Integer, x})]
(* True *)

but

MatchQ[{4, Null}, x : (Null | {_Integer, x})]
(* False *)

What's the right syntax for the desired pattern?

---

BTW, I could have sworn that I've seen recursive Mathematica patterns of this sort before, and almost certainly in the main Mathematica documentation, but I can't find whatever I think I saw. If my memory is correct, I'd appreciate a pointer to the place in the docs where these are documented. Admittedly, my batting average with the Mathematica documentation is frustratingly low in general, but it is particularly bad when it comes to questions regarding patterns. Therefore I would appreciate any pointers to the documentation that may shed light on this post's question.

---

^{1Those familiar with Lisp will see a formal similarity between this pattern and the canonical Lisp list. But note that here I'm not considering $\text{Null}$ and $\{\}$ as equivalent.}

Answer 1

What you need is something like this:

patt = Null | (x_ /; MatchQ[x, {_Integer, patt}] )

The trick is to delay the evaluation for the recursive part, until run-time (match attempt), and Condition is one way to do it. So:

MatchQ[#, patt] & /@ {Null, {4, Null}, {3, {4, Null}}, {2, {3, {4, Null}}}, {1, {2, {3, {4, Null}}}}}


(*  {True, True, True, True, True} *)

and

MatchQ[#, patt] & /@ {{}, {Null}, {Null, Null}, {3, 4, Null}}

(* {False, False, False, False} *)

Recursive patterns have been discussed in a number of places, for example:

• How to match expressions with a repeating pattern
• How can I construct a recursive pattern guard
• Convert recursive regular expression to StringExpression
• Arbitrarily deep nested pattern matching (answer by WReach)
• Generic nested menus implementation (the menuTreeValidQ function)

Answer 2

Not sure if this is what you are looking for, but let´s see (wash, rinse, repeat):

test = {Null, {4,Null}, {3, {4,Null}}, {2, {3, {4,Null}}}, {1, {2, {3, {4, Null}}}},
       {}, {Null}, {Null, Null}, {3,4, Null}};

MatchQ[Null, # //. {_Integer, Null} -> Null] & /@ test

(*{True, True, True, True, True, False, False, False, False}*)

Answer 3

We can apply the method I used for How to match expressions with a repeating pattern:

test[Null | {_Integer, _?test}] = True;
_test = False;

Confirmation:

good = {
  Null,
  {4, Null},
  {3, {4, Null}},
  {2, {3, {4, Null}}},
  {1, {2, {3, {4, Null}}}}
 };

bad = {{}, {Null}, {Null, Null}, {3, 4, Null}};

test /@ good
test /@ bad

{True, True, True, True, True}

{False, False, False, False}

test itself is not a pattern but _?test is as used within the function.

I argue that my method has advantages over Leonid's patt.

Speed

test is an order of magnitude faster than patt:

patt = Null | (x_ /; MatchQ[x, {_Integer, patt}]);

big = Nest[{RandomInteger[9], #} &, Null, 5000];
$RecursionLimit = Infinity;

MatchQ[big, patt]   // RepeatedTiming
MatchQ[big, _?test] // RepeatedTiming

{0.0241, True}

{0.00232, True}

test can be made a bit faster still in this case by using a form that converts to iteration but that method is somewhat less general I think:

Clear[test]

test[{_Integer, x_}] := test[x]
test[Null] = True;
_test = False;

$IterationLimit = Infinity;
MatchQ[big, _?test] // RepeatedTiming

{0.00184, True}

Evaluation

Although not needed in your particular example it can be important for expression tests to not cause unwanted evaluation. The test function can be made to handle this properly by merely setting the Attribute HoldAll. Suppose instead of Null you were looking for foo and your nested head were arbitrary:

ClearAll[test]
Attributes[test] = {HoldAll};

test[foo | _[_Integer, _?test]] = True;
_test = False;

Now even if foo is assigned a value this does not fail:

foo = 1;

test @ Hold[2, {3, {4, foo}}]

True

Notably all that is needed to control the evaluation behavior is a simple SetAttributes or ClearAttributes rather than a fundamental rewriting of the pattern. Changing the behavior of Leonid's patt requires more invasive modification that cannot as easily be switched on and off:

patt = HoldPattern[foo] | (x_ /; MatchQ[Unevaluated @ x, _[_Integer, patt]])

Answer 4

Another way that seems efficient:

pat = Module[{check},
    check[_Integer, Null] := Null;
    check[___] := Throw[False];
    Catch[# /. List -> check /. {Null -> True, _ -> False}]
    ] &;

test = {
 Null, {4, Null}, {3, {4, Null}}, {2, {3, {4, Null}}}, {1, {2, {3, {4, Null}}}},  (*True*)
 {}, 5, {Null, {5, Null}}, {{5, Null}, 4}, {Null}, {Null, Null}, {3, 4, Null}}   (*False*)

pat /@ test
(*
  {True, True, True, True, True,
   False, False, False, False, False, False, False}
*)

On many short matches using Block instead of Module improves efficiency; on larger lists, the difference is negligible. One could hide check in a private context, e.g. foo`check if using Block and you're worried about superseding a definition of check in the Global` context.

---

An eensy bit faster and less code, adapting a suggestion by Leonid Shifrin:

pat = Module[{check},
    check[_Integer, Null] := Null;
    check[___] := Return[False];
    # /. List -> check /. {Null -> True, _ -> False}] &;

(Again, one can substitute Block as describe above.)