Purity can be measured by two things:
- Does the function always return the same output, given the same input; i.e. is it referentially transparent?
- Does the function modify anything outside of itself, i.e. does it have side-effects?
If the answer to 1 is yes and the answer to 2 is no, then the function is pure. Closures only make a function impure if you modify the closed-over variable.
You have described an effect system. It’s true that there are other effect systems than monads, but in practice monads give you a lot of expressive power that you would need to reinvent in any practical effect system you might devise.
For example:
- I start by tagging my I/O procedures with an
io effect.
- My pure functions can still throw exceptions, but throwing exceptions isn’t
io, so I add an exn effect. Now I need to be able to combine effects.
- I want to have non-I/O functions that use mutation internally on a local heap
h, and I want the compiler to make sure that my mutable references don’t escape their scope, so I add an st<h> effect. Now I need parameterised effects.
- For higher-order functions, I need to write multiple versions for every combination of effects I want to support—for example,
map with a pure function versus map with an impure function. Now I need effect polymorphism.
- I notice that my user-defined type could be used to model effects (benign failure, nondeterminism) that the language doesn’t have natively. Now I need user-defined effects.
Monads support all of these use cases:
- Functions that may return errors can use the
Either monad.
- Effects can be combined with monad transformers—if I need exceptions and I/O, I can use the
EitherT IO monad.
- Monads can be parameterised like any other type; the
ST h monad lets you do local mutation on STRefs in the scope of a heap h.
- Because of the
Monad typeclass, I can overload an operation to work on any kind of effect. For example, mapM :: (Monad m) => (a -> m b) -> [a] -> m [b] works in IO, but it also works in Either or ST or any other monad.
- All monads are implemented as user-defined types, except for things like
IO and ST which must be implemented in the Haskell runtime.
There are of course some significant warts in Haskell’s use of monads for side effects.
For one thing, monad transformers are generally not commutative, so StateT Maybe is different from MaybeT State, and you have to be careful to choose the combination that you actually mean.
The bigger problem is that a function can be polymorphic in which monad is being used, but it cannot be polymorphic in whether a monad is being used. So we get loads of duplicated code: map vs. mapM; zipWith vs. zipWithM, &c.
Now, in answer to your actual question…
Koka from Microsoft Research is a language with an effect system that does not suffer from these problems. For example, the type of Koka’s map function includes a type parameter e for effects:
map : (xs : list<a>, f : (a) -> e b) -> e list<b>
And this parameter can be instantiated to the null effect, making map work for pure and impure functions alike. In addition, the order in which effects are specified is immaterial: <exn,io> is the same as <io,exn>.
It’s also worth mentioning that Java’s checked exception mechanism is an example of an effect system that people have widely accepted, but I don’t feel it adequately answers your question because it’s not general.
Best Answer
As long as all values used in the function are defined solely by its parameters, it's a pure function.
The facet that output is the same each time for the same input is controlled by whether the parameters are pure. If you assume the parameters (like a function argument) are also pure, then it is pure.
In a language like Javascript where purity isn't enforced, this means that it's possible to make an otherwise pure function have impure behavior by invoking an impure function passed as a parameter.
This effectively means that for languages that don't enforce purity (ie almost all), it's impossible to define a pure function which invokes functions passed as arguments. It's still useful to write them as pure as possible, and to reason about them as pure functions, but you have to exercise caution because the assumption that it's pure will be broken if you pass in the wrong arguments.
In my experience in practice this isn't usually a big deal - I find it rare to have impure functions be used as function arguments to pure functions.