A higher-order function is a function that takes another function, or a closure, as a parameter. In Rust, there are three somewhat unusual traits that allow us to specify a function or closure as a parameter's trait bound: Fn, FnOnce, and FnMut.

The differences between these traits are defined by what kind of variable access they permit:

• FnOnce is the most widely applicable of these traits, because it has the fewest requirements on what types can implement it. An FnOnce only guarantees that it is safe to call it once. A function that consumes self is an example of a natural FnOnce, because having consumed self, it no longer has a self to be called on in future. Functions and closures that are safe to be called more than once still implement FnOnce, because calling them exactly once isn't an error. That means that a variable that is constrained to be an FnOnce can accept any sort of function or closure.
• FnMut is the next most widely applicable trait. An FnMut guarantees that it is safe to call it more than once, but it doesn't promise not to change variable values elsewhere in the code via mutable borrows. A function that uses &mut self is an example of a natural FnMut, because it might change one or more of the variables contained in its self. Functions and closures that can't or don't actually change any outside variables still implement FnMut, because using them in a place where mutating is allowed isn't an error.
• Fn is the least applicable, since it guarantees that it can be called multiple times and it will not change any outside variables. Anything that is Fn can safely be used where an FnMut or FnOnce was expected, but the reverse is not true.

That means that when we're the receiver, we should prefer to accept FnOnce if possible, or FnMut as a second choice, and Fn as the last choice when we truly need all of those guarantees, so as to give the people who are sending the data value to us the maximum flexibility in what they choose to send.

Here is a very simple higher-order function, which uses a trait bound to specify what kind of function can be assigned to the f parameter:

fn higher_order(f: impl FnOnce(u32) -> u32) {
    f(5);
}

So, that looks a little odd. FnOnce(u32) -> u32 is the complete name of the trait that we're requiring data types for f to implement. The special syntax that allows us to specify the parameter and return types for Fn, FnMut, and FnOnce is unique to those traits; we can't do similar things anywhere else.

Just to be clear, that function definition could have also been written as follows:

fn higher_order2<F>(f: F) where F: FnOnce(u32) -> u32 {
    f(5);
}

We could also have written the same thing as follows:

fn higher_order3<F: FnOnce(u32) -> u32>(f: F) {
    f(5);
}

All of the preceding code means the same thing: the function's f parameter needs to implement the FnOnce trait, and accept a single u32 parameter, and return a u32. 

Here's a bit of code that calls our higher_order function and passes it a closure to be used as the value of f:

let mut y = "y".to_string();
higher_order(|x: u32| {
    y.push('X');
    println!("In the closure, y is now {}", y);
    x
});
println!("After higher_order, y is {}", y);

This closure has one parameter named x, defined between the | and | symbols, but it also accesses the y variable that was defined on the first line. In addition, it changes the value of that variable, meaning it requires mutable access. Thus, this closure implements FnOnce and FnMut, but not Fn.

If we change higher_order to require the Fn trait and try compiling this code, we get a compiler error, as shown in the following screenshot:

This error is not particularly illuminating. What it means is that we told higher_order to require an Fn, and then we passed it a closure that therefore must be an Fn, but we tried to perform a mutating operation inside of the closure, where we don't have a mutable borrow because Rust is sure that the closure must have the Fn trait, so it reports an error about trying a mutating operation on a non-mutable variable.

All we need to do to fix this is change the trait bound on the higher_order function's f parameter back to FnOnce (or FnMut) so that the closure is allowed to perform the push operation on y.

Once we restore f to have the proper trait bound, what does this code actually do?:

1. Creates a mutable variable y containing a String
2. Constructs a closure that captures a mutable borrow of the y variable, and accepts an x parameter
3. Passes that closure to higher_order as the value of the f parameter
4. higher_order then calls f (which is our closure), passing it 5 as the value of its x parameter
5. Within the closure, the following occurs:
   1. The character 'X' is appended to the string stored in y
   2. The new value of y is printed
   3. The value of x is returned, and becomes the result of the f(5) expression
6. higher_order returns
7. The current value of the y variable is printed

Both of the printouts of y print the string yX, because they are both referring to the same actual variable, whether directly or via a mutable borrow.