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?


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 *)
|improve this answer|||||
  • $\begingroup$ Very interesting. This has taught me something. Thank you! $\endgroup$ – Shredderroy Feb 24 '16 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




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

MatchQ[lst, _?test]  (* True *)
|improve this answer|||||
  • $\begingroup$ Thank you very much for that. I will keep your recommendation in mind now. $\endgroup$ – Shredderroy May 26 '16 at 18:42

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.