# Why does this recursive pattern guard not work?

I have the following list:

lst = {
"str 1,1",
{"str 1,2,1", "str 1,2,2"},
{
(* Inner list 1 *)
{"str 2,1", {"str 2,2,1"}, {{"str 3,1", {"str 3,2,1", "str 3,2,2"}, {}}}},
(* Inner list 2 *)
{"str 4,1", {"str 4,2,1"}, {{"str 5,1", {"str 5,2,1", "str 5,2,2"}, {"str 5,3"}}}},
(* Inner list 3 *)
{"str 6,1", {"str 6,2,1", "str 6,2,2"}, {}}
}
};


The list lst is a three-element list, and is intended to have the following structure: the first element is a string; the second element is a list of strings, possibly empty; the third element is either the empty list, or a list of strings, or a list whose members have the same recursive structure as lst.

I have constructed the following pattern guard for lst:

ptn = {_String, {___String}, {___String} | (a_ /; MatchQ[a, {ptn..}])};


This guard works when the third element of lst contains any one of the three inner lists shown. It also works when the third element of lst contains Inner list 1 and Inner list 3, or Inner list 2 and Inner list 3, but not when it contains Inner list 1 and Inner list 2.

Can you please correct the pattern guard?

• Feb 23, 2016 at 20:59
• @Dr.belisarius I also tried ptn = {_String, {___String}, a_ /; MatchQ[a, {___String} | {ptn..}]} but to no effect. Feb 23, 2016 at 21:13

Recursive patterns are tricky. I suggest you to browse this site for different approaches.

In the current case you have to include patterns to match both ptn and lists of ptn:

ptn = {_String, {___String}, {___String} |
(a_ /; MatchQ[a, ptn ..]) | (a_ /; And @@ (MatchQ[#, ptn ..] & /@ a))};

MatchQ[lst, ptn]
(* True *)

MatchQ[{"a", {}, {}}, ptn]
(* True *)

MatchQ[{"a", {"b"}}, ptn]
(* False *)

l = {u, {u, {v, {u, {u, v}}}}} /.
u -> Sequence @@ {"a", {"b"}} /. v -> {"a", {"b"}, {"c"}}
(* {"a", {"b"}, {"a", {"b"}, {{"a", {"b"}, {"c"}}, {"a", {"b"}, {"a", {"b"},
{"a", {"b"}, {"c"}}}}}}} *)

MatchQ[l, ptn]
(* True *)

• Very interesting. This has taught me something. Thank you! Feb 24, 2016 at 2:37

For the second time I shall recommend that you adopt a different method to recursive patterns. This method has demonstrable advantages of efficiency, brevity and evaluation control.

The needed code:

test[{_String, {___String}, {___String} | _?test | {__?test}}] = True;

_test = False;


Borrowing belisarius's examples for testing:

lst            // test
{"a", {}, {} } // test
{"a", {"b"}}   // test

l = {u, {u, {v, {u, {u, v}}}}} /. u -> Sequence["a", {"b"}] /.
v -> {"a", {"b"}, {"c"}};

l // test

True

True

False

True


As explained before converting this predicate function test into a pattern is as simple as _?test:

MatchQ[lst, _?test]  (* True *)

• Thank you very much for that. I will keep your recommendation in mind now. May 26, 2016 at 18:42