Forall and Exists in Scala

def forall(s: Set, p: Int => Boolean): Boolean = {  
    def iter(a: Int): Boolean = {
        if (contains(s, a) && !p(a)) false        // If the predicate condition fails, return false and exit loop (all values don't satisfy the condition).
        else if (a > bound || a < -bound) true    // Out of bounds, return true and exit loop.
        else iter(a-1)                            // Keep looping
          }
        iter(bound) // bound is some integer we plug in, e.g. 2000
      }

The above shows Scala code for the forall function, which takes in a predicate function and a set, and checks every value in the set if they satisfy the predicate. If the predicate is not satisfied for any element in the set, forall returns false. If all elements in the set satisfy the predicate, forall returns true.

In set theory, the inverse of forall is the exists function, where if any value satisfies the predicate, exists returns true. If all elements in the set do not satisfy the predicate, exists returns false.

Using anonymous functions, we can define exists as:

    def exists(s: Set, p: Int => Boolean): Boolean = !forall(s, (x: Int) => !p(x))

Why does this work? There are two steps involved here.

1. The forall function is negated.
2. The p(x) function, or the predicate function, is negated.

Lets take the forall function and name it exists, then lets apply these steps to them the old-fashioned way.

1.     def forallexists(s: Set, p: Int => Boolean): Boolean = {
           def iter(a: Int): Boolean = {
               if (contains(s, a) && !p(a)) true        // If the predicate condition fails, return false and exit loop (all values don't satisfy the condition).
               else if (a > bound || a < -bound) false    // Out of bounds, return true and exit loop.
               else iter(a-1)                            // Keep looping
           }
               iter(bound)
         }
   

This takes care of Step 1.

1.     def exists(s: Set, p: Int => Boolean): Boolean = {
           def iter(a: Int): Boolean = {
               if (contains(s, a) && p(a)) true        // If the predicate condition fails, return false and exit loop (all values don't satisfy the condition).
               else if (a > bound || a < -bound) false    // Out of bounds, return true and exit loop.
               else iter(a-1)                            // Keep looping
           }
               iter(bound)
         }
   

Note that the negation of !p(a) is simply p(a).

And there you have it. We now have the exists function.