# How to define a recursive pattern?

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

$$\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.

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:

• @Mr.Wizard You are right, strictly speaking (although the form of the construct is similar). I removed that link, and added some other, including some of those you mentioned. Jul 1 '15 at 13:53

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}*)

• That's a neat solution. Thank you! It's not quite what I asked for, but I can use it all the same to take care of my immediate task. Unless in the next few hours someone does post the recursive pattern of the question (or confirms via a comment that, my recollection notwithstanding, such pattern is actually not possible in Mathematica), I'll accept your answer.
– kjo
Jun 11 '15 at 15:59
• @kjo yeah, it´s not a a pattern as such... I am also very curious what other solutions will crop up! Glad it helps you in any case :D Jun 11 '15 at 16:03
• Concise, and quick, +1
– ciao
Jun 12 '15 at 6:53
• @cia much appreciated :D Jun 12 '15 at 6:57

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

{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]])

• +1, good stuff. In fact, I've been well aware of this method - for my purposes I came up with it back in 2009, in this post (the menuTreeValidQ function at the start of the code section). Perhaps, the only reason I didn't include it here was the lack of time for an extended post at that moment. What I didn't realize however, is that there is such a speed difference, although in retrospect this seems rather understandable. In any case, this is a great contribution. Jun 30 '15 at 14:15
• @Leonid Thanks. Interesting that in your original use you used MatchQ which appears to be somewhat less efficient and also introduces evaluation unless Unevaluated is added. I didn't realize benefit of the form in this answer until you forced me to work it out in the prior (linked) question. (Thanks again!) Since that time I have tried to make it my standard pattern for problems like this. Jul 1 '15 at 6:57
• I agree, your form is superior in a number of ways. I think I picked the one with MatchQ simply because it was the first thing that came to my mind, I wasn't revisiting older discussions (including my own answers). Shows once again that one should always check what was done before. Interestingly, while I did remember the SO question on deep pattern matching, I forgot about the more recent one you linked, already on SE. It might be a good idea to have some post eventually that would summarize recursive patterns, perhaps in the design patterns question. Jul 1 '15 at 13:26
• @Leonid I guess MatchQ is just more intuitive; also I was drawn to the elegance of the idea of an anonymous function/pattern so it's what I tried to use ("Old method") until your subtle critique forced to consider evaluation behavior. Then I realized how inelegant that form became. Re: "design patterns" I don't know that I could do much better than a rephrasing of this post; is that still worth posting there? Jul 1 '15 at 14:04
• AFAIK, no new answers have been added to that question, but that seems the right place to put this stuff. I might do that as well, or we can collaborate on it. But I think this can wait. Jul 1 '15 at 19:23

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. foocheck 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.)

• +1. You can use check[___]:=Return[False, ReplaceAll] and get rid of Catch - Throw (untested here, but did similar things before). Jun 11 '15 at 20:21
• @LeonidShifrin Thanks, I often forget about Return. In this case just a plain Return worked. On the input pat[{Null}], your suggested form gave an error, "Return::nofunc: Function ReplaceAll not found enclosing Return[False,ReplaceAll]. >>", but I don't know how to explain that. Inserting a Print[Stack[]] shows there is indeed a ReplaceAll above the Return. Jun 11 '15 at 23:06
• It is probably because ReplaceAll isn't HoldAll. Rojo has explained that in his post on the second argument of Return. Jun 12 '15 at 18:03
• @LeonidShifrin Yes, Rojo's explanation seems consistent with this behavior. Thanks. Jun 12 '15 at 18:13