21
$\begingroup$

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.

Improve this question
$\endgroup$
1

4 Answers 4

Reset to default
27
$\begingroup$

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:

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ @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. $\endgroup$
    – Leonid Shifrin
    Jul 1, 2015 at 13:53
15
$\begingroup$

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}*)
Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – kjo
    Jun 11, 2015 at 15:59
  • $\begingroup$ @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 $\endgroup$
    – Yves Klett
    Jun 11, 2015 at 16:03
  • $\begingroup$ Concise, and quick, +1 $\endgroup$
    – ciao
    Jun 12, 2015 at 6:53
  • $\begingroup$ @cia much appreciated :D $\endgroup$
    – Yves Klett
    Jun 12, 2015 at 6:57
9
$\begingroup$

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]])
Improve this answer
$\endgroup$
5
  • $\begingroup$ +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. $\endgroup$
    – Leonid Shifrin
    Jun 30, 2015 at 14:15
  • $\begingroup$ @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. $\endgroup$
    – Mr.Wizard
    Jul 1, 2015 at 6:57
  • $\begingroup$ 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. $\endgroup$
    – Leonid Shifrin
    Jul 1, 2015 at 13:26
  • $\begingroup$ @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? $\endgroup$
    – Mr.Wizard
    Jul 1, 2015 at 14:04
  • $\begingroup$ 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. $\endgroup$
    – Leonid Shifrin
    Jul 1, 2015 at 19:23
8
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ +1. You can use check[___]:=Return[False, ReplaceAll] and get rid of Catch - Throw (untested here, but did similar things before). $\endgroup$
    – Leonid Shifrin
    Jun 11, 2015 at 20:21
  • $\begingroup$ @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. $\endgroup$
    – Michael E2
    Jun 11, 2015 at 23:06
  • $\begingroup$ It is probably because ReplaceAll isn't HoldAll. Rojo has explained that in his post on the second argument of Return. $\endgroup$
    – Leonid Shifrin
    Jun 12, 2015 at 18:03
  • $\begingroup$ @LeonidShifrin Yes, Rojo's explanation seems consistent with this behavior. Thanks. $\endgroup$
    – Michael E2
    Jun 12, 2015 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.