Successful match in Replace but not in Cases?

Question

I have a little example that exhibits a successful pattern match in ReplaceAll that Cases misses and I wonder if the assembled sages would be so kind as to offer me an explanation?

This is chopped from an original Prolog emulator by Renan Cabrera circa 2000.

ClearAll[k,s,l,m,j,f,w,g,a,b]

Consider an unordered sequence of statements s stored in a knowledge base k, each being a predicate l about some terms m, f, j, and w:

k=s[l[m,f],
    l[m,w],
    l[j,w],
    l[j,m]
];

We wish to search this knowledge base for any predicates such that l[m,X_] and l[j,X_], where X_ matches the same term in both predicates. Our first cut is something like

k /. s[l[m,X_],l[j,X_]] -> a[X]
(* Out[42]:= s[l[m,f],l[m,w],l[j,w],l[j,m]] *)

but this doesn't work until we make s flat and orderless (associative and commutative):

SetAttributes[s,{Flat,Orderless}]

and now

k /. s[l[m,X_],l[j,X_]] -> a[X]
(* Out[43]:= s[a[w],l[j,m],l[m,f]] *)

This is, of course, just the same as ReplaceAll[k, s[l[m,X_],l[j,X_]] -> a[X]]. (notice the canonical reordering in the output), and now I can extract my answer with something like

Cases[k /. s[ l[m, X_], l[j, X_] ]->a[X],a[Y_]->Y]
(* Out[44]:= {w} *)

The surprise and the question is why doesn't this work?

Cases[k, s[ l[m, X_], l[j, X_] ] -> a[X]]
(* Out[45]:= {} *)

or even this

MatchQ[k, s[ l[m, X_], l[j, X_] ]]
(* Out[46]:= False *)

It's as though ReplaceAll, Cases, and MatchQ are using different pattern matchers.

Will be grateful for advice, clues, discussion, etc.

Answer 1

MatchQ looks to see if the whole expression matches the pattern, so you need to add a blank to allow for the other elements of s:

MatchQ[k, s[l[m, X_], l[j, X_], ___]]

Cases takes a list and checks each element in turn, so I think the pattern matcher only gets to see each l[a,b] in isolation. The best I could come up with is:

Cases[Subsets[k, {2}], s[l[m, X_], l[j, X_]] -> a[X]]

Further investigation

Here are a couple of questions about Cases I have tried to answer experimentally. I don't know if this helps anyone else much, but it was useful for me to go through it and I think I now understand how Cases behaves, even if the why is a mystery.

Q1. Does Cases take into account Orderless ?

In[1]:= SetAttributes[a,{Orderless}]
In[2]:= Cases[a[x,y],a[y,_]->0,{0}]
Out[2]= {0}

A1. Yes, it does. The pattern matcher understands that a[x,y] === a[y,x] which matches the pattern.

Q2. Does Cases take into account Flat ?

In[3]:= SetAttributes[a,{Flat}]
In[4]:= Cases[a[x,y,z],a[onebit_,anotherbit_]:>{onebit+anotherbit},{0}]
Out[4]= {{a[x]+a[y,z]}}

A2. Yes, it does. The pattern matcher understands that a[x,y,z] === a[a[x],a[y,z]] which matches the pattern.

Q3. Given that Cases can use the above transformation, will it get a "hit" on the pattern a[x] ?

In[5]:= Cases[a[x,y,z],a[x]->b,{0,Infinity}]
Out[5]= {}

A3. No, even though the transformed expression a[a[x],a[y,z]] clearly contains a match for a[x] at level 1, this doesn't count. Cases appears to require the entire expression at level n to match the pattern. The logic appears to be:

• Level 0: expression a[x,y,x] does not match a[x]
• Level 0: transformed expression a[a[x],a[y,z]] does not match a[x]
• Level 1: expression x does not match a[x]
• Level 1: expression y does not match a[x]

etc...

This is in contrast to ReplaceAll, which does pick up the a[x] in the transformed expression:

In[6]:= a[x,y,z]/.a[x]->b
Out[6]= a[b,y,z]

So it seems like ReplaceAll applies Flat and Orderless transformations outermost, and then for each transformed expression it digs down into the subexpressions looking for a match. Whereas Cases digs down into the subexpressions of the untransformed original expression outermost, and for each subexpression it tries the various Flat and Orderless transformations looking for a match.

I realise this is probably a complete misrepresentation of how the pattern matcher actually works, but as a hand-waving mental picture it seems to explain the different behaviour of Cases and ReplaceAll

Answer 2

I suspect that the difference relates to the fact that Cases traverses depth-first, while ReplaceAll traverses breadth-first. This can be seen here:

k = s[l[m, f], l[m, w], l[j, w], l[j, m]];
test = (Print[##]; False) &;

k /. x__?test :> Null;

s[l[m,f],l[m,w],l[j,w],l[j,m]]
s
l[m,f]
l
m
f
l[m,w]
l
m
w
l[j,w]
l
j
w
l[j,m]
l
j
m

Cases[k, x__?test, {0, -1}, Heads -> True];

s
l
m
f
l[m,f]
l
m
w
l[m,w]
l
j
w
l[j,w]
l
j
m
l[j,m]
s[l[m,f],l[m,w],l[j,w],l[j,m]]