Can Higher Order Functions Be Pure in C++?

cfunctional programming

I was thinking about pure functions especially in the context of C++, which of course is not a purely functional language, and was wondering if higher order functions in C++ can ever be considered pure? Take for example std::find_if: it would be very pure except it takes another function, which might not be pure. There seems to be no constraint on the predicate std::find_if takes that prevents doing nasty, impure things inside the function, like this:

const std::vector<int> v = { 1,2,3,4,5 };
auto result = std::find_if(v.begin(), v.end(), [](int arg)
{
   return arg < someGlobalVariable;
} );

So maybe someone with more experience in functional programming languages could clarify this for me: Does the notion of 'pure functions' make sense when dealing with higher order functions?

EDIT: I should have stated more clearly that I am not looking for an explanation of const correctness in C++. I just wanted to know if the definition of a pure function makes sense when talking about higher order functions in C++. I changed the example to illustrate that const is not solving my problem here!

Best Answer

You're right, this is an issue when one wants to reason about purity of functions in a language that permits impure functions. Technically almost all languages allow impurity, but the purely functional ones usually explicitly mark the impure ones in the type system, such that the Haskell function map :: (a -> b) -> [a] -> [b] does, implicitly, require that the function to be mapped is pure.

Informally, we can certainly say: find_if is pure only if the predicate function is pure. So how might we teach the compiler about this?

Since C++ does not mark impure functions (nor pure ones, for that matter, but let's pretend we are adding that feature), and we probably don't want to restrict find_if to only accept pure functions (since that would be backwards incompatible), we are left with what I'll dub purity polymorphism. That is, find_if is pure iff the function passed in is pure. I'm not aware of a language doing this, but in principle it is no different from polymorphism over types (a.k.a. generics). Sufficently sophisticated effect systems probably have equivalent capability, just generalized to more and more fine-grained judgements than "pure" and "impure".

Related Solutions

Functional Programming – Dependency Inversion and Higher-Order Functions

Dependency Inversion in OOP means that you code against an interface which is then provided by an implementation in an object.

Languages that support higher language functions can often solve simple dependency inversion problems by passing behaviour as a function instead of an object which implements an interface in the OO-sense.

In such languages, the function's signature can become the interface and a function is passed in instead of a traditional object to provide the desired behaviour. The hole in the middle pattern is a good example for this.

It let's you achieve the same result with less code and more expressiveness, as you don't need to implement a whole class that conforms to an (OOP) interface to provide the desired behaviour for the caller. Instead, you can just pass a simple function definition. In short: Code is often easier to maintain, more expressive and more flexible when one uses higher order functions.

An example in C#

Traditional approach:

public IEnumerable<Customer> FilterCustomers(IFilter<Customer> filter, IEnumerable<Customers> customers)
{
    foreach(var customer in customers)
    {
        if(filter.Matches(customer))
        {
            yield return customer;
        }
    }
}

//now you've got to implement all these filters
class CustomerNameFilter : IFilter<Customer> /*...*/
class CustomerBirthdayFilter : IFilter<Customer> /*...*/

//the invocation looks like this
var filteredDataByName = FilterCustomers(new CustomerNameFilter("SomeName"), customers);
var filteredDataBybirthDay = FilterCustomers(new CustomerBirthdayFilter(SomeDate), customers);

With higher order functions:

public IEnumerable<Customer> FilterCustomers(Func<Customer, bool> filter, IEnumerable<Customers> customers)
{
    foreach(var customer in customers)
    {
        if(filter(customer))
        {
            yield return customer;
        }
    }
}

Now the implementation and invocation become less cumbersome. We don't need to supply an IFilter implementation anymore. We don't need to implement classes for the filters anymore.

var filteredDataByName = FilterCustomers(x => x.Name.Equals("CustomerName"), customers);
var filteredDataByBirthday = FilterCustomers(x => x.Birthday == SomeDateTime, customers);

Of course, this can already be done by LinQ in C#. I just used this example to illustrate that it's easier and more flexible to use higher order functions instead of objects which implement an interface.

C++11 Support for Higher-Order List Functions

Even more, C++ have such functions, take a look to algorithm (or with C++11 additions) header:

std::transform
std::for_each
std::remove_copy_if

They can be easily used with any container.

For example your code can be expressed like this (with C++11 lambdas for easy coding):

std::vector<int> x = {1, 2, 3, 4, 5};
std::vector<int> y;
std::transform(x.begin(), x.end(), std::back_inserter(y), [](int elem){ return elem * elem; });

Less intuitive, but you can easily wrap the std::transform call into function which would return new container (with move semantics for better perfomance).

Best Answer

Related Solutions

Functional Programming – Dependency Inversion and Higher-Order Functions

C++11 Support for Higher-Order List Functions

Related Topic