On 2011-06-15 17:38, Charles McAnany wrote:
> Hi, all. I'm implementing a little linked list that selection-sorts itself.
> Basically, the sort code is: swap this element with the minimum element in
> the list.
> sort the rest of the list.
>
> Obviously, one part of this is swapping elements. It seemed easiest to swap
> the contents of two nodes, rather than messing with rearranging the
> elements.
> Now, that description of swap sounds impure, right? But this compiles:
> private pure void swap(SortableListNode other){ //SortableListNode is a
> class. T temp = this.datum;
> this.datum = other.datum;
> other.datum = temp;
> }
> Am I missing the point of pure somehow? Am I going crazy? (The sort does
> work, so the elements are being mutated.)
There are two types of pure functions: weakly pure and strongly pure. Pure
functions (of either variety) cannot access mutable global variables. Any pure
function can be called from any other pure function, but you can't call impure
functions from pure functions. Strongly pure functions are pure functions
whose parameters are either immutable or implicitly convertible to immutable.
Calls to strongly pure functions can be optimized out within an expression.
For instance, something like
5 * abs(a) * abs(a)
would only call abs once and would just use the result of the first call again
rather than making a second function call. Calls to weakly pure functions, on
the other hand, cannot be optimized out. This is because they can affect the
state of their arguments and each call to them could have differing results.
However, because they can only affect the state of their arguments and not any
global state, they're safe to call from within strongly pure functions.
The function that you have there is weakly pure. Its argument is a mutable
reference, which cannot be implicitly convertible to immutable, so calls to it
cannot be optimized out. However, it _can_ be called from a strongly pure
function.
Originally, all we had were strongly pure functions, but they were far too
limiting, because so few functions can be strongly pure. So, weakly pure
functions were introduced, which makes it possible to make many more functions
strongly pure.
- Jonathan M Davis
