How to do logical tests for all list elements in mathematica

Question

I have a list and I want to apply a logical test to each element, and if any one of them does not satisfy this condition, then return false. I want to write this in Mathematica or find a built-in function, but seems ForAll does not actually do that.

My question is: how to do this most efficiently?

Bonus: how about similarly for Exists function: i.e. if there is any element in the list satisfy the condition, return true.

Answer 1

The answer to the first portion of your question might be something along these lines:

forAll[list_, cond_] := Select[list, ! cond@# &, 1] === {};

which is used like this:

forAll[{1, 2, 3, 3.5}, IntegerQ]

---

The "exists" function is already natively implemented as MemberQ. It could be reimplemented as:

exists[list_,cond_] := Select[list, cond, 1] =!= {};

Use it like

exists[Range@100, (10 == # &)]

which returns true as 10 is an element causing the Select to return {10} which is not equal to {}.

Answer 2

This answer is not intended to show the most efficient method, but rather an alternative method that serves the pedagogical purpose of showing some important core functionality in Mathematica.

nixeagle's answer avoids explicitly testing every element of the list. If the test doesn't lend itself to inclusion in the third argument of Select, then the below might be useful.

To do this, you need to learn about the standard Or and And functions, as well as the Map (/@) and Apply (@@) commands which are extremely important for any Mathematica user to learn. (see this tutorial)

Here is a simple example.

In[2]:= data = RandomInteger[{0, 10}, {10}]

Out[2]= {10, 1, 0, 10, 1, 5, 2, 2, 4, 1}

In[4]:= # > 5 & /@ data

Out[4]= {True, False, False, True, False, False, False, False, False, \
False}

In[6]:= And @@ (# > 5 & /@ data)

Out[6]= False

What is going on here is that you are mapping the function ("greater than 5") to each element of the list using Map, to get a list of True/False values. You are then applying the standard logical function And to the whole list to get the single Boolean value.

These are all very much core functionality in Mathematica and I recommend you read the documentation for these functions carefully and practice using them.

This is not the most efficient method, but for small problems you will not notice the difference.

In[11]:= Do[Select[data, ! # > 5 &, 1] === {}, {10000}] // Timing

Out[11]= {0.031, Null}

In[12]:= Do[And @@ (# > 5 & /@ data);, {10000}] // Timing

Out[12]= {0.11, Null}

For Exists, the alternative to Select would be MatchQ for patterns or MemberQ for explicit values. The documentation has some useful examples.

Answer 3

Not to be taken too seriously, but this

ClearAll[existsC];
existsC[cond_] := With[
  {c = cond},
  Compile[
   {{l, _Integer, 1}},
   Module[
    {flag = False, len = Length@l},
    Do[
     If[cond[l[[i]]],
       flag = True; Break[];
       ];,
     {i, 1, len}];
    flag
    ],
   CompilationTarget -> "C"
   ]
  ]

appears to be around 300 times faster than nixeagle's solutions on my machine. What this does is to emit a compiled function which takes a list and compares its elements to the given condition (fixed at compile-time), returning True if any of them matches.

It is used as follows: Compile with the appropriate cond, eg

t = existsC[# == 99999 &];

and then

t[Range@100000] // timeIt

returns 2.33376*10^-6 (a worst-case scenario, as I am just searching linearly and the matching element is at the end) while

exists[Range@100000, (99999 == # &)] // timeIt

returns 0.000237162 (here, timeIt is this).

Answer 4

A pattern based approach:

forAll[list_, test_] := MatchQ[ list, _[__?test] ]

MemberQ already implements exists.

---

Mathematica 10 has a new function for this: AllTrue. When all elements pass the test my function appears to be a bit faster:

a = Range[2, 1*^7, 2];

AllTrue[a, EvenQ] // Timing // First
forAll[a, EvenQ]  // Timing // First

1.014007

0.936006

However with an early exit the benefit of the new function becomes apparent:

a[[123456]] = 1;

AllTrue[a, EvenQ] // Timing // First
forAll[a, EvenQ]  // Timing // First

0.031200

0.265202

Answer 5

Even though && and || perform short-circuit evaluation, i.e., don't evaluate their arguments unnecessarily, I suspect that solutions based on Select[] or Map[] won't benefit much from this. That's because they apply the logical test to every element, building a list of Boolean truth-values before performing the conjunction/disjunction among them. If the test you've specified is slow, it can be a real bottleneck.

So here is a variant that does short-circuit evaluation of the condition as well:

allSatisfy[list_, cond_] :=
   Catch[Fold[If[cond[#2], True, Throw[False]] &, True, list]]

Testing if any element in the list satisfies the condition is nicely symmetric:

anySatisfy[list_, cond_] := 
   Catch[Fold[If[cond[#2], Throw[True], False] &, False, list]]

Of course this could equally have been done (and candidly speaking, more easily) using procedural loops such as While[], but I have a soft spot for functional programming!

Answer 6

nixeagle got the bonus part, but the way I would've done the first part is as follows:

AllSatisfy[expr_, cond_] := Length@Select[expr, cond] == Length@expr

Answer 7

There's a simple solution:

In[1401]:= a = {1, 2, 3}

Out[1401]= {1, 2, 3}

In[1398]:= Boole[Thread[a[[2]] == a]]

Out[1398]= {0, 1, 0}

In[1400]:= Boole[Thread[a[[2]] >= a]]

Out[1400]= {1, 1, 0}

In[1402]:= Boole[Thread[a[[2]] != a]]

Out[1402]= {1, 0, 1}

Success!