# Evaluation of Alternatives

I recently stumbled upon a few examples that suggest patterns containing Alternatives do not evaluate for individual alternatives. For example:

SetAttributes[f, Flat];
f[a,b,c] /. f[a, f[b,c]|other] -> post
(* f[a,b,c] *)


Edit: The first example (above) evaluates to post in version 11 and higher. As explained by Daniel Lichtblau in the comments, this example was a long-running issue at the intersection of Flat and Alternatives. It's nice to see it's fixed now. (End edit.)

and (a somewhat contrived example)

g[2] /. g[ 1 + (1|other) ] -> post
(* g[2] *)


Is this behavior documented anywhere? I would have expected Alternatives to behave equivalently to providing the alternate rules separately.

Furthermore, is my claim above true, that no further evaluation occurs when the individual alternatives are tested, for all cases? Or is there something special going on here?

Lastly, is there an elegant workaround so that the first example evaluates to post? Obviously I'd like to avoid writing the enveloping f[a, ... ] twice.

• I have been out of this for a while, but I don't think f[a, f[b, c]] actually matches f[a,b,c]. It evaluates to it, and then it matches it. If you do f[a,b,c]/.HoldPattern@f[a,f[b,c]]:>post you also don't get a match
– Rojo
Feb 2 '16 at 16:23
• @Rojo Yes, this combined with the fact that the pattern is not evaluated further when individual alternatives are tried seems to answer the question. See the answer I just posted. But why does f[a, f[b,c]] fail to match f[a,b,c]? Doesn't the documentation for the Flat attribute explicitly say it's accounted for in pattern matching? (Perhaps I should write another question about this...) Feb 4 '16 at 9:53
• @jjc385 That's a good question, and one I wish I could answer at the moment. I think at one time I did work my way to a better understanding with Rojo's help but it seems to have slipped from me now. Anyway take a look at these Q&A's: (304), (5067), (18060) Feb 4 '16 at 10:29
• MatchQ[2,1+(1|other)] will return False for a number of reasons (e.g. 2 is an atom so cannot match something with Head of Plus). Also I should mention that MatchQ does not itself use Thread, as is done in some proposed approaches to get your desired outcome. Think of it as syntactic matching rather than mathematical equivalence testing. That's an oversimplification though: the "correct" structure in which this pattern matching dwells involves expression trees, if that helps to think about what's happening in these examples. Feb 5 '16 at 18:25
• It is difficult to separate evaluation from pattern matching. The matcher works iteratively but with back-tracking for situations where that is needed. So first it will check for expr having head of patt. If so it will check that first arg is x. Then it hits the Alternatives and goes through an iterate-until-match loop. If there are multiple matches it bails at the first...But if what follows later has Alternatives (say) and a dependency on the prior patterns that only matches when a later match from the earlier Alternatives worked, then a backtrack happens... Feb 6 '16 at 23:59

The two examples in this question relate to two different aspects of pattern matching. I will start with the simpler to understand and intentional aspect, which is the second example.

g[2] /. g[ 1 + (1|other) ] -> post
(* g[2] *)


In the above, the pattern doesn't match, and it can never match. g[2] has one argument. Since Plus is OneIdentity, 2 catch match Plus[2], Plus[Plus[2]], and so on, but it can never match a 2-argument Plus, which is what the pattern contains. The "expanded" pattern g[1 + 1] | g[1 + other] -> post seems to work, only because it evaluates:

In[20]:= g[1 + 1] | g[1 + other] -> post
Out[20]= g[2] | g[1 + other] -> post


It wouldn't matter if we used RuleDelay, because that only prevents the RHS from evaluating. Moreover, if we used HoldPattern to prevent the LHS from evaluating, it doesn't match:

In[22]:= g[2] /. HoldPattern[g[1 + 1] | g[1 + other]] -> post
Out[22]= g[2]


This may not be explicitly documented, but it is absolutely the design: the pattern matcher accounts for attributes, sequences, and so forth, but it does not simulate evaluation. Beyond the fact that evaluation may have undesired side effects, we would have a true circularity problem given that evaluation is done via pattern-matching! Pattern matching compares the structure of one expression against another structure, to see if rules (replacement, evaluation, etc.) should fire.

Your first example is an occurence of a long-standing implementation issue. It's even more suprising given the following:

In[23]:= SetAttributes[f, Flat];
f[a, b, c] /. f[a, f[b, c] | o_ /; o === other] -> post
Out[24]= post


Weird, right? There are a few issues here, but the main one is that the pattern matcher treats literal patterns like f[b,c] and general patterns like o_ slightly differently (mainly for reasons of efficiency), but sometimes these two sets of rules conflict with each other and we end up with inconsistencies like the above. We have some improvements in the pipeline and ideas on how to completely clean this up, but unfortunately completely squashing all these issues is a ways off.

• Great answer. This kind of insight from the inside is really valuable to those of us trying to understand the system from the outside! IMO it would be a good idea to include this inconsistency as a "Possible Issue" in the documentation for Flat or Alternatives. Feb 6 '16 at 21:48
• "Beyond the fact that evaluation may have undesired side effects, we would have a true circularity problem given that evaluation is done via pattern-matching!" I never thought of it like that, but it makes perfect sense. Thanks for a pithy summary of the evaluation thing. Feb 7 '16 at 4:46
• "We have some improvements in the pipeline and ideas on how to completely clean this up, but unfortunately completely squashing all these issues is a ways off." I am really happy to know that development continues on the core functions, and not only on library extension. Feb 7 '16 at 4:50
• @SimonWoods The same thought had occurred to me. I'm going to try to carve out some time this month to improve the documentation. Feb 7 '16 at 23:12
• Hi Guys. I'm pleased to report that the first example in this question is fixed in our internal development version. Moreover, this week I completed the 4th and final review of bunch of documentation updates to our core pattern matching functions. So when our next release comes, be on the lookout for new examples in ReplaceAll, Replace, Flat, and several releated pages! Jun 26 '16 at 21:24

I think an acceptable solution is to Thread over Alternatives:

### Basic solution:

SetAttributes[f, Flat];
f[a, b, c] /. Thread[f[a, f[b, c] | other], Alternatives] -> post

post


Though, it won't be very helpful in more complex situations: f[a | b, f[b, c | h]].

## General solution (experimental)

tupplesOver[
f[a | g, f[b, c | h] | other],
Alternatives
]

f[a, b, c] | f[g, b, c] | f[a, b, h] | f[g, b, h] | f[a, other] |  f[g, other]


Maybe it will be better shown when we drop Flat attribute from f:

ClearAll[f];
tupplesOver[
f[a | g, f[b, c | h] | other],
Alternatives]

f[a, f[b, c]] | f[g, f[b, c]] | f[a, f[b, h]] | f[g, f[b, h]] |
f[a, other] | f[g, other]


### Code

tupplesOver[expr_, head_] := Module[{temp, myAlternatives},
temp = myAlternatives[expr /. head -> myAlternatives];
SetAttributes[myAlternatives, Flat];

Function[arg,
Module[{pos},
pos = First@Reverse@Sort@Position[arg, _myAlternatives];
MapAt[
arg,
Most@pos
]
]
],
temp,
(Count[#, myAlternatives, \[Infinity], Heads -> True] > 1) &
]
]


IMO it may be desired although I wouldn't say expected. Maybe someone more experienced will tell us why things are the way they are :)

• +1 for elegance! Though I'm worried about how well it generalizes. For example (taking f=Times for concreteness), Thread[a*(b*x | y)*(u | c*v), Alternatives] gives a b x u | a y c v, which doesn't work the way I expect from Alternatives. Now I'm thinking of performing a replacement on the pattern involving Alternatives. For example, performing a*(b*x | y)*(u | c*v)//. {Times[a_, Verbatim[Alternatives][b_Times, c_]] :> a b | a c, Times[a_, Verbatim[Alternatives][c_, b_Times]] :> a b | a c} works in this case, but is proving nontrivial to generalize. Feb 2 '16 at 8:21
• Actually, now I'm thinking it might be better to implement a rule on Alternatives itself that implements the functionality I expect: g_[a___, x_Alternatives, b___] /; ! g === Alternatives :> (g[a, #, b] &) /@ x. Note that this requires ReplaceRepeated, and I think it's been guarded against infinite recursion. I believe it acts as I expect in all examples given so far (including your more complicated one). Feb 2 '16 at 8:31
• Small quibble -- your 'more complex' example actually works as I naively expected, without any manipulation, because f[ g[a,b], f[ d, g[c,h] ]] evaluates to f[ g[a,b], d, g[c,h] ] whether g is Alternatives or anything else. But I think I understand your point -- it's similar to more complex example I gave in my first comment -- f[ a, f[ (f[b,x] | y), (u | f[c,v])] ]. (It looks a lot more readable with f=Times.) Still present after edit, which I'm still looking over. Feb 2 '16 at 9:03
• Nice solution! Please correct me if I'm wrong, but I believe it functions identically to a dressed up version of what I wrote in my first comment: altProcess[patt_] := Flatten[ patt //. (g : Except[Alternatives])[a___, x_Alternatives, b___] :> (g[a, #, b] &) /@ x , Infinity, Alternatives]. It can even be generalized to altProcess[patt_, head_] := Flatten[ patt //. (g : Except[head])[a___, x_head, b___] :> (g[a, #, b] &) /@ x , Infinity, head]. @Kuba, do you see any difference in function? (I prefer patterns, so my way seems more natural to me ;) Feb 2 '16 at 10:00
• @jjc385 I think you should self answer, it seems to be better :)
– Kuba
Feb 2 '16 at 10:04

After discussing with Kuba, I conjecture the following:

Patterns involving alternatives are not evaluated further when attempting to match each alternative

That is, somePattern[..., a|b, ...] originally evaluates as if a|b is a black box. Then, during pattern matching, the pattern does not evaluate any further when a|b is replaced by a and b in turn.

To the best of my knowledge, this behavior is not documented anywhere.

Personally, I find this behavior somewhat surprising -- in particular, I would intuitively expect the following patterns to be completely equivalent:

somePattern[..., a|b, ...]
somePattern[..., a, ...] | somePattern[..., b, ...]


As far as I can tell, nothing in the documentation suggests the two patterns above should not be equivalent. I'd be very interested to hear whether anybody has conflicting intuition, or any idea why Alternatives would be built this way.

I suppose there might be guiding principles behind deciding whether expressions are to be evaluated further, that could motivate this implementation. The only other case I know of where an expression is (meaningfully) not evaluated further is in the case of a global variable changing value which would influence the evaluation via a Condition. (See my previous question, How is LHS = RHS; … ; LHS (nontrivially) different from … ; RHS. ) It seems to me that this sort of behavior is not documented well anywhere.

Forcing equivalence of alternatives

As stated above, I intuitively expect the following patterns to be equivalent:

somePattern[..., a|b, ...]
somePattern[..., a, ...] | somePattern[..., b, ...]


That is, I expect one pattern to match a given expression if and only if the other pattern also matches that expression.

Inspired by Kuba's attempts, I create a function which can be applied to patterns to force the behavior I expect -- essentially that patterns thread over Alternatives :

threadAlt[patt_] := Flatten[
patt //. (g : Except[Alternatives])[a___, x_Alternatives, b___]
:> (g[a, #, b] &) /@ x ,
Infinity, Alternatives]


I believe it functions identically to Kuba's topplesOver if generalized to

threadAlt[patt_, head_] := Flatten[
:> (g[a, #, b] &) /@ x ,


In particular, this 'solves' the examples in the original question:

SetAttributes[f, Flat];

(* f[a, b, c] | f[a, other] *)

f[a,b,c] /. f[a, f[b,c]|other] -> post
(* f[a,b,c] *)

f[a,b,c] /. threadAlt@f[a, f[b,c]|other] -> post
(* post *)


Edit: Loose ends

As mentioned above, I don't see anything in the documentation that suggests Alternatives should function differently from my intuition (i.e., how my threadAlt function forces it to behave). I'm very curious about why Alternatives might be implemented the way it is, rather than the way I suggest.

In particular, I'm curious why Mathematica would not further evaluate a pattern when attempting to match each alternative. See discussion above.

Personally, I find this behavior somewhat surprising -- in particular, I would intuitively expect the following patterns to be completely equivalent:

somePattern[..., a|b, ...]
somePattern[..., a, ...] | somePattern[..., b, ...]


While that may seem a natural expectation I do not believe the documentation ever states that they are. Nowhere can I find the claim that Alternatives evaluates in the same manner as separate patterns, or that patterns evaluate like their component parts. To the contrary I make frequent use of the fact that they do not.

An example from Pattern matching on Orderless functions inside Hold:

MatchQ[Hold[1 + 2], Hold[(h : Plus)[2, _]]]   (* False *)


The Pattern prevents Plus from messing with argument order as it does in:

MatchQ[Hold[1 + 2], Hold[Plus[2, _]]]         (* True *)


Likewise if we have a function f that evaluates undesirably on f[_Integer] we can block that with a Pattern or Alternatives:

f[Except[1]] := "Fail!"

MatchQ[f[1], f[_Integer]]
MatchQ[f[1], (x : f)[_Integer]]
MatchQ[f[1], (f | f)[_Integer]]

False

True

True


I don't know why this design was chosen and I don't think I've ever given it much thought. I have just accepted this as the nature of patterns in Mathematica.

• (A subset of) exactly what I was looking for -- an example of how the implemented behavior could possibly be useful. It seems these features of patterns are well-hidden! +1 Feb 4 '16 at 11:17
• That first is typically handled with HoldPattern. Something like In[65]:= MatchQ[f[1], HoldPattern[f[_Integer]]] Out[65]= True. (I realize you know this, not sure if it is generally clear though.) Feb 4 '16 at 15:41
• @Daniel Yeah, I probably should have included that. Thank you. Feb 4 '16 at 15:54
• Also (as noted in another comment) Flat and Alternatives do not get along very well. Feb 5 '16 at 0:58