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:
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:
Basic operations
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:
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:
From Wikipedia:
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.In computer science, a set is an abstract data structure that can store certain values, without any particular order, and no repeated values.
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.
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.
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.