10

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.

Improve this question
2
  • Would you perhaps be looking for And and/or Or? (I like the way that sounds. But it might look better as (&&)^2 (||)^2 ) ForAll and Exists really are not meant for this although they can be adapted. Example: Resolve[ForAll[x, x == 1 || x == 2 || x == 3, x > 2.5]] will return False. Commented Dec 14, 2011 at 22:44
  • 1
    This question has been asked before here, in fact more than once. See here: stackoverflow.com/questions/4181470/…, and here: stackoverflow.com/questions/4911827/… Commented Dec 15, 2011 at 9:11

7 Answers 7

Reset to default
9

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 {}.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Damn. I was about to post an answer when I realized it was the same exact thing you posted.
This is a really fast accept, perhaps you should uncheck my answer for a bit and see if others manage to do any better :). Plus I've only really answered the second part of your question, though with a bit of (correct) tweaking you can answer the first part of the question as well.
Yeah which is why I removed it once I realized it was not answering the question properly. And using Length after collecting up the full list of elements is not really efficient at all.
Length should be O(1) for lists in Mathematica, IIRC. It is inefficient in use of memory though, since you're creating the list then getting it's length. Most functional solutions in Mathematica seem to suffer from memory issues.
@MikeBantegui Right, I've edited this to do something a little less wasteful of memory :)
8

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.

Improve this answer

8 Comments

This is not good. All elements are tested even if the first one fails.
@Mr.Wizard This problem has been addressed in full in the previous incarnations of this question (which is a duplicate. A pity I only saw it now) - here: stackoverflow.com/questions/4181470/…, and here: stackoverflow.com/questions/4911827/…
@Mr.Wizard Perhaps, it's too late for that (or may be not). It is just a pity that the aspect you mentioned is not emphasized enough (although acl'a and Hideric Browne's solutions take that into account, but acl's is a more specialized for numeric lsists, while Hideric's is a bit careless with exceptions).
@Mr.Wizard I took the viewpoint that it was better to educate the OP about some Mathematica basics, given the content of the question, than worry about efficiency.
@Mr.Wizard I had forgotten that. I will amend my answer to make it clear that I am not purporting to demonstrate the most efficient approach.
|
4

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).

Improve this answer

7 Comments

+1 for showing a really cool way to make use of Compile and making me think of (defmacro ...) in Common Lisp! This is probably my first interesting encounter with what some folks call Mathematica "meta" programming. And yes I'd love to know why "WVM" is faster. Finally not to dampen the pure awesomeness of this answer... but I strongly suspect that this is only valid for numbers, not symbols or anything else Compile won't work with (though I wish it did work with more stuff!).
@nixeagle thanks! you're right, it won't work with lists of objects not supported by Compile, or with inhomogeneous lists etc.
+1. You don't need the outer With - the rules (parameter-passing) have (almost) the same semantics and can also be used to inject stuff. As for the timings, on my machine C-compiled code is much faster than WVM - compiled (as we would expect), which contradicts your observation.
By the way, here is a shorter version of your code: existsC[cond_] := Compile[{{l, _Integer, 1}}, Do[If[cond[el], Return[True]], {el, l}] == True, CompilationTarget -> "C"]. It might also be a tiny bit faster.
@Leonid thanks. Using Null==True to return False is clever, even if it forces me to have to think when I read the code.
|
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
Improve this answer

Comments

1

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!

Improve this answer

2 Comments

I would use tagged exceptions which are safer. For an implementation which uses that but otherwise is similar to your suggestion, see the second part of my answer here: stackoverflow.com/questions/4911827/…
The third argument of Select allows it to "short-circuit" the test after the first match.
0

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
Improve this answer

Comments

0

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!

Improve this answer

Comments