Monday, January 2, 2012

Predicates, Tests, and Test Patterns: How to Build Your Own

Build Your Own: User-defined Examples

Xiangdong Wen of Tech Support noted that the hard part of constructing Predicates is considering all the possible inputs and exceptions. To do a thorough job, we might need to do a Piecewise definition of a Predicate, or define a Predicate with Which, and if desired leave an error message as the final condition at the bottom to catch any exceptions that escaped us.

Limit a Built-in Predicate: lessThanOneQ

lessThanOneQ@x_ := If[ x1 < 1, True, False]

testSet = Range[0, 1.5, .3]

{0., 0.3, 0.6, 0.9, 1.2, 1.5}

lessThanOneQ /@ testSet

{True, True, True, True, False, False}

Test for Specified Length: lengthTwoQ

Clear@lengthTwoQ; lengthTwoQ@x_ := If[Length@x == 2, True, False]

lengthTwoQ /@ {{x, y}, {y, x}, {x, y, z}}

{True, True, False}

Test for Meeting Boolean Combination of Conditions: BinaryQ

By setting the Attributes of our Predicate to Listable, we shortcut the need to use Map over a List.

ClearAll@BinaryQ; SetAttributes[BinaryQ, Listable];
BinaryQ@x_ := If[x === 1 || x === 0, True, False ]

BinaryQ@{0, 3, 1, 1., 2}

{True, False, True, False, False}

One can also use Boolean And (&&) similarly, or any combination of And and Or in a compound Expression.

Test for Membership in a Set: integerLessThan10Q

Here we make a Predicate from a test for an element's membership in a defined set.

integerLessThan10 = Range@10

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

integerLessThan10Q@x_ := If[MemberQ[integerLessThan10, x], True, False]

integerLessThan10Q /@ {4, 4/5, Pi, 3, 11, 251/25}

{True, False, False, True, False, False}

More Examples: maxEqualQ, maxNearQ, valueAtQ, positionNearQ

Different Predicates can test for a variety of related conditions. These are functions I used to test properties of book bestseller lists but here I use random lists for illustration. The first one tests to see if the maximum value of two lists of numbers are the same.

maxEqualQ[x_List, y_List] := If[Max@x == Max@y, True, False]

list1 = RandomInteger[{0, 25}, 20] // Sort

{0, 2, 2, 4, 5, 6, 8, 8, 9, 9, 9, 11, 15, 16, 16, 17, 17, 19, 19, 19}

list2 = RandomInteger[{0, 25}, 20] // Sort

{1, 2, 5, 6, 6, 6, 9, 12, 13, 14, 17, 17, 18, 18, 23, 23, 24, 24, 25, 25}

maxEqualQ[list1, list2]

False

This tests to see if difference between the maximum of two lists is less than a specified magnitude.

maxNearQ[x_List, y_List, nearness_Integer] :=
 If[Abs[Max@x - Max@y] <= nearness, True, False]

maxNearQ[list1, list2, 10]

True

maxNearQ[list1, list2, 1]

False

This tests to see if the Position of the maxima of two lists is the same.

maxPositionEqualQ[x_List, y_List] :=
 If[Position[list1, Max@x] == Position[list2, Max@y], True, False]

maxPositionEqualQ[list1, list2]

False

Using Predicates in Select, Cases, and Related Filter Functions

As you look at these simple examples realize they are but a glimpse of the power of this type of usage that I mentioned at the start of this section. The Predicates, Conditions and Boolean conjunctions used in these filter functions can be arbitrarily complex, and as Mangone notes we are only restricted to anything that Mathematica can compute.

First we define a Predicate and use pure Function since those are idioms that Select uses, then we just use Condition in Cases, since that is the syntax that Cases uses. Consequently I recommend using the Q suffix when naming a Predicate used in Select. Note in the Cases example the additional restriction to Reals using a Head test.

Consider using Predicates in the related filter functions Count, Position, Tally, Gather, Sort, SortBy, etc.

Clear@lessThanOneQ; lessThanOneQ@x_ := If[ x < 1, True, False]

Select[Range[-0.2, 1.1, 0.2], lessThanOneQ]

{-0.2, 0., 0.2, 0.4, 0.6, 0.8}

Select[Range[-0.2, 1.1, 0.2], # < 1 &]

{-0.2, 0., 0.2, 0.4, 0.6, 0.8}

Function[x, x < 1] /@ Range[-0.2, 1.1, 0.2]

{True, True, True, True, True, True, False}

Cases[Range[-0.2, 1.1, 0.2], x_Real /; x < 1]

{-0.2, 0., 0.2, 0.4, 0.6, 0.8}

lessThanOnePositiveQ@x_ :=
 If[0 < x < 1 , True, False](* version restricted to positive numbers *)

lessThanOnePositiveQv2@x_ :=
 If[x < 1 && Positive@x, True, False] (* alternate version *)

Select[Range[-0.2, 1.1, 0.2], lessThanOnePositiveQ]

{0.2, 0.4, 0.6, 0.8}

Select[Range[-0.2, 1.1, 0.2], lessThanOnePositiveQv2]

{0.2, 0.4, 0.6, 0.8}

Predicate Using a Piecewise Function

Note the usage in the Named Pattern variable of a NumberQ predicate to allow both Reals and Integers. This example is intended to illustrate that a Piecewise-defined Predicate can include an unlimited number of orthogonal conditions.

Clear@pieceWiseElementQ; pieceWiseElementQ@number_?NumberQ :=
 Piecewise[{{False, number < -3}, { True, -3 < number < 0}, {False,
    0 <= number <= 6}, {True, number > 6}, {True, number === 4.5}}]

pieceWiseElementQ /@ {-3.00001, -0.0000000001, -4/5, 0, 0.000000001, 4/5, 4.5,
   6, 6.01, 9}

{False, True, True, False, False, False, False, False, True, True}

Predicates, Tests and Test Patterns: NumberQ, NumericQ, Equal, SameQ

NumberQ and NumericQ

NumberQ is more restrictive than NumericQ and seems to be True only if the evaluated expression is explicitly a number, while NumericQ tests for a "numeric quantity," which seems to mean that Mathematica tests each component to see if its fully evaluated form is a number. NumberQ probably also contains exceptions that should be considered "numeric," for instance all of the built-in numerical constants. More Predicates are implicit in built-in defined sets, such as Rationals and Reals (see below).

NumberQ@3.14159

True

NumberQ@Pi

False

NumericQ@Pi

True

NumberQ@Sqrt@2

False

Both Predicates will test a compound expression, but only NumericQ will test the fully evaluated form of each component. If any component evaluates False by NumberQ, the whole expression evaluates as False.

NumberQ[Sqrt@2 + 5]

False

NumericQ[Sqrt@2 + 5]

True

NumberQ@Sin@Sqrt@2

False

Since in the end the sine of the square root of 2 evaluates to a Real, NumericQ tests it as True; in effect it's testing 0.987766, while NumberQ cannot see the evaluated form.

Sin@Sqrt@2 // N

0.987766

NumericQ@Sin@Sqrt@2

True

Equal (==) and SameQ (===)

The distinction between these two Predicates can be confusing, but the basic idea is Equal tests for numeric equality while SameQ tests for syntactical equality. There are subtleties; here Mathematica compares Pi using its internal storage form.

N[Pi, 4] == N[Pi, 6]

True

However if we compare explicitly different numbers Equal will return False.

3.141 == 3.14159

False

SameQ will pick up syntactic differences that Equal misses.

Pi === N[Pi, 5]

False

Here is a nice example from a good introduction to Mathematica by Nancy Blachman and Colin Williams of using SameQ to test syntax in a paradigm for testing user input for a correctness (Mathematica, A Practical Introduction, 2nd ed., p 433, syntax modifications mine).

testUser1[question_, correctAnswer_] :=
 Module[{userAnswer = Input@question},
  If[userAnswer === correctAnswer, Print@"Correct!",
   Print["You said ", userAnswer, " but the correct answer is ",
    correctAnswer] ]
  ]


testUser1["What is Newton's second law of motion?", f = ma]

Correct!

It is easy to see how using Equal or StringMatchQ would give different tests for equality ("What is the square root of 2?") or an exact string match ("What is the largest continent?") in user input.

Part 3 will show how to build and use your own user-defined Predicates.

Predicates, Tests and Test Patterns: Introduction and Significance

The Importance of Predicates

In his excellent Mathematica Cookbook (p. 149), Sal Mangano said about using a predicate:

"This is a powerful construct because it extends the degree of control over the matching process to any criteria Mathematica can compute." 

Mangone's example used a predicate to further qualify a Pattern (see Pattern Assignment, in Assignment in this book), which alone is a powerful device, but his is a general comment about predicates in a language as flexible as Mathematica's and when Mathematica is considered as a technical computing universe containing, for instance, curated scientific and financial data, the ability to import web pages, and a universal representation ("everything is an expression") for diverse data such as graphics, sound, and images.

In logic, a predicate is a set whose elements can be evaluated as True or False, or more simply, a predicate is a test of something that is either True or False. They can be simple or complex. Predicates are very handy in Mathematica, since it is quite common to apply conditions to lists or expressions, or to test elements of lists or expressions. Predicates are an implicit If test implemented in an intuitively useful way. John Gray notes that predicates are also a way of constructing data types, and interestingly, that John von Neumann based a version of set theory on predicates (Mastering Mathematica, 2nd ed., p 242).

Most of Mathematica's built-in predicates have a "Q" as their suffix, signifying that they ask a question. They are discussed in guide/TestingExpressions. Predicates are designed to return True if they exactly match a pattern and False if there is no precise match.

A precise match means that built-in predicates have subtle differences, e.g. Equal and SameQ, NumberQ and NumericQ, VectorQ, MatrixQ and ArrayQ. And capturing what we wish to be True in our own predicates can require some tinkering (see this post).

Predicates without a Q in their name are listed here.

Let's look at Mathematica's built-in predicates , and then we'll make our own. The new-in-10 function Multicolumn produces a nicely-formatted table easier than using Partition and TableForm.

Names@"*Q" // Multicolumn[#,5]&



We'll take a look at how to use Mathematica's Predicates in Part 2.

Assignment to a Pattern


I'll use a couple of examples on searching Strings from Sal Mangano's excellent Mathematica Cookbook to show how to use Pattern Assignment. First, it's simple enough to search some Strings for those that are numbers:

StringMatchQ[{"12345", "2468", "abcde"}, NumberString]

{True, True, False}

But if you want to add a Predicate, you need another device such as naming a Pattern and using the name in the Predicate. This is an example of Pattern Assignment where the Pattern is named "m".

StringMatchQ[{"12345", "2468", "abcde"}, m : NumberString /; OddQ@FromDigits@m]

{True, False, False}

As Sal Mangone notes in his Mathematica Cookbook and I explore further in Predicates, Tests, and Test Patterns, adding a Predicate to a Pattern is a powerful device because we can include in the Predicate anything that Mathematica can compute. A Predicate can be a built-in one or one we construct, so the possibilities are truly limitless.