Can higher order functions ever be pure?

Question

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!

Answer 1

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".

Answer 2

There is a constraint on the predicate, but it's textually enforced by standard text and may be enforced by a sufficiently capable compiler as Quality-of-Implementation.

Many things are only guarded by phrasing in the standard. Some of the rationale is that while its possible to constrain the predicate to ones that take the argument by value or const reference, it would make it harder to use existing predicates and spawn a horde of adapters just to get the function to fit.

Similiarly, the standard doesn't forbid modification of the predicate, but it warns that it may and probably will make copies of it, so mutation needs to be done via external or captured state.

When designing a C++ library, it's commonly said that you cannot envision all the places it'll be used, just that you should try to not constrain them too hard.

I would guess that a concept or trait that would declare a pure function would not gain the implementation anything, as it's already designed around the programmer promising that the predicate doesn't modify the collection. Similarly, a diagnostic that indicates that a predicate is impure would fire on pretty much everything and doesn't aid much.

C++11 25.1/6 states (paraphrased): If the Effects section of an algorithm says that a value pointed to by any iterator passed as an argument is modified, then that algorithm has an additional type requirement, it shall satisfy the requirements of a mutable iterator (24.2).

C++11 25.1/8 (and /9) states: ... a predicate may not apply any non-constant function through the dereferenced iterator.

find_if (25.2.5) has no such effects section, so even if the predicate was allowed to mutate, it would still not be legal.