8
$\begingroup$

I am modelling binary trees in Wolfram Language by writing them as three-element lists, like so: binTree = {nodeVal, leftChild, rightChild}.

It does not yet matter what kind of structure nodeVal itself has, but let us assume, for the sake of this problem, that the structure is a list of two integers: nodeValPattern = {_Integer, _Integer}.

Furthermore, leftChild and rightChild can be either {} or have internal nodes of the same shape as binTree itself.

I would like to have a pattern guard for the structure of binTree. The naive attempt does not work:

nodeValPattern = {_Integer, _Integer};
binTreePattern = {nodeValPattern, ({} | binTreePattern), ({} | binTreePattern)};
binTree = {
    {{1, 2}, {{2, 3}, {}, {}}, {}},
    {{3, 4}, {}, {{4, 5}, {}, {}}},
    {}
};
MatchQ[binTree, binTreePattern]

I get the following error:

$RecursionLimit::reclim: Recursion depth of 1024 exceeded. >>

Can you please help?

$\endgroup$
8
$\begingroup$

Your pattern has itself in its own definition. Mathematica will keep substituting the definition in at each level until it runs out of stack. From this answer about recursive string matching we can see a potential solution: using MatchQ instead of the explicit pattern, since Condition will prevent the recursive part of the pattern from being evaluated when it's defined.

Condition // Attributes
(* {HoldAll, Protected} *)

Thus we can try this:

binTreePattern2 = {nodeValPattern, ({} | (a_ /; 
     MatchQ[a, binTreePattern2])), ({} | (b_ /; 
     MatchQ[b, binTreePattern2]))};

MatchQ[binTree, binTreePattern2]
(* False *)

It turns out your tree is not correctly formed! (Look at binTree // TreeForm). Here is an example of a correctly formed tree.

binTree2 = {{10, 11}, {{1, 2}, {{2, 3}, {}, {}}, {}}, {{3, 
   4}, {}, {{4, 5}, {}, {}}}};

MatchQ[binTree2, binTreePattern2]
(* True *)
| improve this answer | |
$\endgroup$
  • 5
    $\begingroup$ +1. To be pedantic, while the answer you linked to was the correct answer to that question, the solution to avoid recursion for that question was proposed first in my earlier answer to it. Another nice use of recursive patterns can be found in this answer. I have also used recursive pattern in a very similar setting in the menuTreeValidQ function in this answer on generic nested menu implementation, back in 2009. $\endgroup$ – Leonid Shifrin Feb 27 '15 at 0:03
  • 1
    $\begingroup$ @Leonid Is there not a question at least fairly similar to (5958128) on this site also? I cannot find it now. Edit: Found it: (11045) $\endgroup$ – Mr.Wizard Feb 27 '15 at 1:52
  • $\begingroup$ @Mr.Wizard Good point! Actually, I completely forgot about that one. My be, because you beat me there :). Anyway, I think that recursive patterns are a very powerful and under-explored technique. I have used more complex versions of it with great effect several times. May be, at some point one of us (you, WReach or myself) would find some time to write a reference post on this topic. Thanks for the ref. $\endgroup$ – Leonid Shifrin Feb 27 '15 at 19:15
2
$\begingroup$

Referencing How to match expressions with a repeating pattern and How to define a recursive pattern? it is in my opinion superior to use a test function definition, which is easily made a pattern with _?test, to using Condition and MatchQ to avoid an infinite loop.

  1. It more easily handles the case should one need to keep parts of the expression unevaluated during testing.

  2. It appears to be more efficient in all cases that I have compared.

For this problem:

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

Or equivalently you can define the function with pattern sub-parts if you prefer, to improve clarity in large patterns:

node = {_Integer, _Integer};
leaf = {} | _?test;

test[{node, leaf, leaf}] := True
_test = False;
  • In either case you could leave out _test = False if test will always be used in _?test but I prefer to make test a complete predicate function.

Now a large tree to your specification for the purpose of testing:

$RecursionLimit = 10000;
make[] := If[RandomInteger[] == 0, {}, {RandomInteger[9, 2], make[], make[]}];
SeedRandom[835];
bigTree = make[];

Size:

Depth[bigTree]
LeafCount[bigTree]
1642

877496

Speed compared to 2012rcampion's binTreePattern2:

MatchQ[bigTree, binTreePattern2] // RepeatedTiming
MatchQ[bigTree, _?test]          // RepeatedTiming
{0.1790, True}

{0.0764, True}
| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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