# Can higher order functions ever be pure?

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!

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

• If something for that was introduced, a look at `noexcept` might be in order. – Deduplicator Aug 14 '15 at 14:10
• "...the Haskell function map :: (a -> b) -> [a] -> [b] does, implicitly, require that the function to be mapped is pure.": To be more precise, I would say that all functions in Haskell are pure, and therefore `map` and the function being mapped are pure. – Giorgio Aug 14 '15 at 18:03
• @Giorgio You could say that, but functions of type `a -> IO b` are the moral equivalent of impure functions, so in the context of this question I don't feel that is a useful position. – user7043 Aug 14 '15 at 18:37
• A function of type `a -> IO b` is still a pure function i.e., given a value of type `a`, it always produces the same action of type `IO b`. Executing the action resulting from function application may not be pure, but executing an action and evaluating a function are two different things in Haskell. – Giorgio Aug 14 '15 at 18:42
• In my intuition `map` is always a pure function. The result of applying `map` to a function may be pure or impure, according to the function that is being mapped. – Giorgio Aug 14 '15 at 18:54

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.

• Thanks for pointing this out. It still doesn't completely answer my question, but the way I understood it this just means that C++ can't enforce purity through code (regarding <algorithm>), so it has to state it in the standard? – Mortano Aug 14 '15 at 11:23