Using a PatternTest versus a Condition for pattern matching

Question

My last question to the site resulted in several answers that involve using pattern matching in Mathematica, a feature I wasn't very familiar with at the time. I am currently reading Mathematica Navigator and am picking up a bit on patterns. Very powerful stuff! My question may not have a definite answer, but I am curious.

When performing pattern matching there are two ways that I see that seem to provide very similar functionality. First there are PatternTests, such as the following:

(* Replace all items in list that fall in the interval [0, 1] with 1
 * using a PatternTest *)
{1, 2, 3, 0.4, 0} /. x_?(0 <= # <= 1 &) -> 1

The PatternTest being the true/false test within the parenthesis after the question mark. Alternatively there are Conditions. Here I accomplish the same as the above but with a Condition:

(* Replace all items in list that fall in the interval [0, 1] with 1
 * using a Condition *)
{1, 2, 3, 0.4, 0} /. x_ /; 0 <= x <= 1 -> 1

Here the Condition is the same true/false test after the /; operator. I [mostly] understand how these work, but I am curious why both of these exist. I can see why one method would be preferable in some conditions while the other would be preferable in other conditions. For instance, a PatternTest seems to be preferable in situations where a simple test is involved:

f[x_Integer?EvenQ] := x+1

And a Condition seems preferable when a more complex condition is required:

f[x_Integer /; EvenQ[x] && Positive[x]] := x+1

Is this the only justification for having both operators? Are there additional details behind-the-scenes that should influence my decision of which one to use or is it purely a matter of preference?

As a bonus, are there any old timers that can give the history of these two methods of pattern matching? I.e, which of these two operators was implemented first in Mathematica?

EDIT

From the answers that have been posted so far, it appears that Conditions have a much wider and more general use case than PatternTests. I wonder if it would be correct to say that the use cases for PatternTest are a subset of the use cases for Condition, and hence PatternTests are merely a syntactic sugar of sorts and is more or less redundant (although still helpful and preferable is some circumstances.) This still begs the question of why PatternTests exist other than as a convenience. This is where a historian might be able to shine some light. If PatternTests were first implemented in Mathematica, then adding Conditions in a later version would add flexibility to the language. However, if the Condition shorthand syntax was first implemented, then was the PatternTest syntax later implemented as a shorthand convenience operator?

Answer 1

I usually consider PatternTest as local to a specific pattern such as x_Integer?Positive and Condition as more general, often involving multiple patterns, e.g.:

f[x_, y_] /; x+y < 10 := x*y

An aspect of PatternTest that is different from Condition is that it is automatically applied to each element of a sequence, whereas Condition applies to the whole. A pattern such as __?EvenQ means a sequences of arguments all of which pass EvenQ. Consider:

f2[x__?EvenQ] := . . .

This is awkward with Condition:

f1[x__] /; (And @@ EvenQ /@ {x}) := . . .

Furthermore the naive method above does not short-circuit on a failure therefore it will be inefficient. This could be fixed but it will be even more clumsy.

Then consider the converse:

f3[x__] /; Plus[x] == 7 := . . .

To do this using PatternTest we would need to apply it to the entire expression f3[x__], complicating its form and risking unwanted evaluation or recursion. (Counterexample: see my proposed solution to Quick way to use conditioned patterns when defining multi-argument function? for where I feel that PatternTest is the best way to proceed.)

There is one rather obscure (at least to me) yet very important use of Condition that extends this generality.

lhs := Module[{vars}, rhs /; test] allows local variables to be shared between test and rhs. You can use the same construction with Block and With.

This is quite unusual in Mathematica's patterns and assignments. It allows execution of code as part of the definition, then testing by a condition based on the result. If the condition fails, the pattern matcher then moves on to search for other matches. The evaluation that occurred can produce side effects but otherwise Mathematica behaves as though the entire pattern (lhs := rhs assignment) did not match.

One elegant use of this functionality is the Trott-Strzebonski method for In-Place Evaluation.

---

Leonid wrote, and encouraged me to include here:

One other thing I want to mention is that with PatternTest, it is easier to inadvertently leak evaluation, while in Condition avoiding that is usually just a matter of inserting Unevaluated in a proper place. I discussed this topic to some extent here

Finally, there are some syntactic differences which are good to keep in mind, for example precedence-related issues like this one.

---

Rojo stated:

Another consequence of this shows when you want to store a pattern in a variable, or inject it with a With. ... Can't do that with Condition unless you want all the instances of the pattern in each definition to be the same.

As a rather contrived counter-example one can use Unique symbols in a pattern constructor:

pat[] := Pattern[#, _] /; # > 4 & @ Unique[]

f[a : pat[], b : pat[]] := {a, b}

f[5, 6]

{5, 6}

Of course it is better to use PatternTest for this, but I think it is useful to show that it can be done.

Answer 2

Condition has three forms in which it can be used in defining a function:

1. f[x_Integer /; EvenQ[x] && Positive[x]] := x+1,
2. f[x_Integer] /; EvenQ[x] && Positive[x] := x+1, and
3. f[x_Integer] := x+1 /; EvenQ[x] && Positive[x]

which are interpreted slightly differently by Mathematica. For instance, the first form results in the Pattern, x_Integer, being interpreted as

Condition[Pattern[x,Blank[Integer]], And[EvenQ[x],Positive[x]]]

or, in short hand

Condition[ x_Integer, EvenQ[x] && Positive[x]]

The second form looks like,

Condition[f[x_Integer], EvenQ[x] && Positive[x]] := x + 1

The third form is interpreted as,

f[x_Integer] := Condition[ x + 1, EvenQ[x] && Positive[x]]

They all give identical results. The timings reveal a slightly different tale:

f0[x_Integer?(And[EvenQ[#], Positive[#]] &)] := x + 1
f1[x_Integer /; EvenQ[x] && Positive[x]] := x + 1
f2[x_Integer] /; EvenQ[x] && Positive[x] := x + 1
f3[x_Integer] := x + 1 /; EvenQ[x] && Positive[x]

rnds = RandomInteger[{-10, 10}, 1000000];

Timing[f0 /@ rnds;]
Timing[f1 /@ rnds;]
Timing[f2 /@ rnds;]
Timing[f3 /@ rnds;]
(*
{1.75124, Null}
{1.41897, Null}
{1.4107, Null}
{2.17659, Null}
*)

The timings for f1 and f2 do exhibit some volatility, and occasionally exceed the timing for f0, but, for the most part, are consistently faster than PatternTest. The timing for f3 is always slower, much slower.

Edit: However, some caution needs to be applied here. With a single condition, such as EvenQ, the results for PatternTest are on par with the results for the first two forms of Condition. Again, the third form is slower, and usually over twice as slow.

Edit - 2: The increase in speed I was seeing when using Function was illusory. The results for simple conditions still holds, though. The more complex conditions using functions is as slow as f3.

(* Note the parantheses around Function *)
f4[x_Integer?(Function[{x}, EvenQ[x]&&Positive[x]])] := x + 1

fcn1[x_] := EvenQ[x] && Positive[x]
f5[x_Integer?fcn1] := x + 1

fcn2 = EvenQ[#] && Positive[#] &
f5[x_Integer?fcn2] := x + 1

(* Timings, respecively
{2.37899, Null}
{1.92366, Null}
{1.86119, Null}
*)

Condition does have the advantage of clarity as you can use the variable names within it directly. An advantage that is not easily overcome.

Answer 3

Adding 1c to the good answers already...

In Condition you need named patterns, and that brings issues when you create composite patterns because all patterns with the same name need to be the same expression.

So let's say you want f to match with a sequence of even arguments. The following works, as noted by Mr.Wizard

f[x__?EvenQ]:=3

But it wouldn't have worked something like

f[(x_/;EvenQ[x])..]:=3

This matches only when all the even numbers are the same number.

Another consequence of this shows when you want to store a pattern in a variable, or inject it with a With. So, you could easily do something like this

With[{myPatt=(_?(EvenQ[#]&&somecomplicatedstuff[#]&))},

f[myPatt, x_Integer]:=blabla;
g[r[myPatt, myPatt]]:=bloblo;
]

Can't do that with Condition unless you want all the instances of the pattern in each definition to be the same.

Answer 4

I tried several variations and here are the two fastest ways I can find to do a simple task.

In:=  data = RandomReal[{-0.2,1}, 10^7];
      Timing[ Count[ data, x_/;Positive[x] ];]

Out= {5.897,Null}

In:=  data = RandomReal[{-0.2,1}, 10^7];
      Timing[ Count[ data, _?Positive ];]

Out= {5.164,Null}

Notice _?Positive is the fastest and most concise.

My intent above was only to compare ?Positive with x_ /; Positive[x]. Afterwards I realized a faster way to count the positive numbers in a long list is the following.

In:=  data=RandomReal[{-0.2,1},10^7];  
      Timing[Count[Positive[data],True];]  

Out=  {0.998,Null}

Next we see the timing differences of Condition and PatternTest are different for a more complicated example.

In:= data = RandomInteger[{-100,100},10^7];  
    Timing[Count[data,x_?(Function[n,And[Positive[n],EvenQ[n]]])];]  

Out=  {20.109,Null}  


In:=  data = RandomInteger[{-100,100},10^7];  
    Timing[ Count[data, x_/;And[Positive[x],EvenQ[x]] ];]  

Out=  {10.717,Null}  


In:= data = RandomInteger[{-100,100},10^7];  
    test[n_] = And[Positive[n],EvenQ[n]];  
    Timing[ Count[data, x_?test[x]]; ]  

Out= {0.546,Null}  


In:= data = RandomInteger[{-100,100},10^7];  
    Timing[ Count[data, x_?(And[Positive[#],EvenQ[#]])&]; ]  

Out= {0.515,Null}  

---

Next I illustrate a point Mr. Wizard mentioned without an example above. Use of /; (Condition) is very helpful here, and PatternTest can't be used in its place.

In:=  OnlyLargeFactors[factored_]:= 10^15 < Min[Part[factored,All,1]];
      foo[n_Integer]:= With[{factors=FactorInteger[n]}, 
          factors/;OnlyLargeFactors[factors]
       ]

The definition of foo isn't used in the first example because the integer has small factors.

In:= foo[10^40+543]

Out= foo[10000000000000000000000000000000000000543]

In the next example the definition is used because the integer has only factors larger than $10^{15}$. If not for the use of Condition we would have to evaluate FactorInteger twice and that can take a long time.

In:= foo[100000000000000109301303000000000001424179]

Out= {{1000000000000001093,1},{100000000000000000001303,1}}

I am using Mathematica version 7, and I the last example works if I use Module instead of With. However, it doesn't work if I use Block.