Here's a variation on a exercise I recently came across recently. We're going to work on representing sets of integers. What's a set?

From Wikipedia:

In computer science, a set is an abstract data structure that can store certain values, without any particular order, and no repeated values.

It's worth repeating that in our exercise, we are dealing with sets of integers, to keep it simple. Accordinlgy, by this definition, we can consider {1, 3, 23, -5, 32, 4} as a set. However, not all sets have a finite number of elements. For instance, we can consider the set of all the negative integers. That makes it difficult to represent with our traditional collections.

For this reason we will represent our sets with a function that tests if an element is part of the set or not. Mathematically speaking, this function is called the characterstic of our set. For instance, in Lua, here's how we'd represent our set of negative integers:

set_of_negative_ints = function(x) return x <= 0 end

And here's how we would represent the singleton {5}:

singleton_5 = function(x) return x == 5 end

The goal of the exercise is to implement common operations on sets, using this functional representation.

Basic operations

union(setA, setB): returns a set containing all the elements in setA and setB.
intersection(setA, setB): returns a set containing all the common elements between setA and setB.
diff(setA, setB): returns a set containing all the elements of setA which are not in setB.
symmetic_diff(setA, setB): returns a set containing all the elements in setA or setB but not in both.

Working with predicates

A predicate is a function that returns a boolean. In our case we will call p a predicate that accepts one integer as argument. Here are some functions to implement to make sets work with predicates:

filter(s, p): returns a set containing all the elements of s where p(element) is true.
all(s, p): returns true if applying p on every element of s returns true every time.
any(s, p): returns true if there exists at least one element of s such as p(element) evaluates to true.

Note: If you're having problems (I am, so far) implementing all(), you could try something simpler to move on with subsequent exercises. Indeed, the only obvious way to do this is to test p on each element of the set. In order to do so, it could be simpler to set a boud high enough (e.g. 1000) and test p on each element going from -bound to +bound. However you should still be able to implement any() in terms of all().

Bonus question
Using the functions we've already defined, implement the function map(s, f) where f is a function that accepts one integer as argument and returns an integer. The map() function should return a set that is the result of applying f on every element of the set s.

For instance:

s = {1, 3, -8}
f = function(x) return x*2 end

assert(map(s, f) == {2, 6, -16})

Hint

Keep in mind that in our representation, a set is a function.
The implementation of each of these functions (except maybe all()) is really short, possibly a one-liner.