Functional sets in C++

I am taking a functional programming class. One of the exercises involves defining sets in terms of functions; since C++ now supports lambdas (and closures), I figured it would be interesting to implement them in C++ (the assignment was in a different language. It is similar to assignments in SICP)

The idea is to define a set (of integers, to simplify), as a function; you pass the element and it returns whether the element is in the set or not. So, we can define a Set as a function that takes a boolean and returns an int. I also define a predicate, which is identical to a set. BTW, I'm using the new std::function  type.

	typedef std::function<bool(int)> Set;
	typedef std::function<bool(int)> Predicate;

view raw 1_typedefs.cpp hosted with ❤ by GitHub

Now, we can define a singletonSet function, that takes an int, and returns a set that contains that int. We need to create a function on the fly, at runtime, and that's what lambdas let us do. We define a lambda with the [] syntax, and the = inside means to capture any variables (make a closure) by value. In this case, we're capturing the elem variable, so every call to singletonSet returns a new lambda, with the right value of elem!

	Set singletonSet(int val) {
	return [=](int x){return x==val;} ;
	}

view raw 2_singletonSet.cpp hosted with ❤ by GitHub

And with that, we can define the union of two sets, as a new function (lambda) that returns true if either set contains the elements, and the intersection as a function that returns true if both sets contain the element, as in the following code:

	Set set_union(Set s1, Set s2)
	{
	return [=](int x){return contains(s1,x) || contains(s2,x);};
	}
	Set set_intersection(Set s1, Set s2)
	{
	return [=](int x){return contains(s1,x) && contains(s2,x);};
	}

view raw 3_union_and_intersection.cpp hosted with ❤ by GitHub

You could use singletonSet and set_union, as follows:

	void demo_union(void)
	{
	Set s1=singletonSet(1);
	Set s2=singletonSet(2);
	Set s3=singletonSet(3);
	Set un=set_union(s1,s2);
	Set all=set_union(s1,set_union(s2,s3));
	cout << contains(s1,2) << endl; // this should print 0 (meaning false :)
	cout << contains(s2,2) << endl; // this should print 1 (meaning true :)
	cout << contains(all,3) << endl; // this should print 1 (meaning true :)
	}

view raw demo_union.cpp hosted with ❤ by GitHub

And set_intersection as follows:

	void demo_intersection(void)
	{
	Set s1=singletonSet(1);
	Set s2=singletonSet(2);
	Set s3=singletonSet(3);
	Set all=set_union(s1,set_union(s2,s3));
	Set s1b=set_intersection(all,s1); // back to s1, since it is the intersection of all=(s1 U s2 U s3)
	Set empty=set_intersection(s1,s2); // empty set ! why ?
	cout << contains(s1b,1) << endl; // what would this print and why?
	}

view raw demo_intersection.cpp hosted with ❤ by GitHub

The assignment had a couple other functions (foreach and exists), and you can find the full source, some unit tests and a demo at my github