Thursday, October 4, 2012

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.
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!
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:
You could use singletonSet and set_union, as follows:
And set_intersection as follows:
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

3 comments:

  1. Why do you need a contains function ? Would it not be enough to implement union as [=](int x) { return s1(x) || s2(x); } ?

    ReplyDelete
  2. Also, you could do with fewer ... dysfunctional ^-^ ... comments if you did `std::cout << std::boolalpha;` too :)

    ReplyDelete
  3. I used contains since the assignment had it :) I like it because it reminds me I'm viewing it as a set, rather than a function.

    And, thanks for reminding about boolalpha :)

    ReplyDelete