Higher-order functions in Rust

Note: this is my first foray into Rust programming, so take everything I say with a life-shortening heap of salt, and please correct me if I get something wrong!

Update (March 18, 2016): For a more detailed (and probably more correct) explanation, see the Returning Closures section of The Rust Programming Language.

Because I’m interested in functional programming, my first attempt to write a Rust program looked something like this:

fn constantly(n : i64) -> fn() -> i64 {
  || n // This is the syntax for an anonymous function in Rust.
}
fn main() {
  println!("{}", constantly(3)());
}

The function constantly takes an integer and returns a function that always returns that integer. For example, constantly(3) is a function that always returns 3, meaning constantly(3)() is 3.

Unfortunately, this program doesn’t compile. Instead, we get the following error:

main.rs:2:5: 2:9 error: mismatched types:
 expected `fn() -> i64`,
    found `[closure@main.rs:2:5: 2:9 n:_]`
(expected fn pointer,
    found closure) [E0308]
[...]

As it turns out, Rust’s “anonymous functions” are in fact “closures”, which have a compiler-generated type that can’t be referenced directly — in this case [closure@main.rs…]. Since we claimed to be returning a fn() -> i64, but returned a [closure@main.rs…] instead, the compiler complained about a type mismatch.

So let’s try returning an actual function:

fn constantly(n : i64) -> fn() -> i64 {
  fn f() -> i64 {
    n
  }
}

This time, the compiler complains about something different:

main.rs:3:9: 3:10 error: can't capture dynamic environment in a fn item; use the || { ... } closure form instead [E0434]
[...]

The problem is that normal Rust functions aren’t closures: they don’t capture the environment in which they’re defined. This means that our inner function f doesn’t look up the value of n until it’s called, at which time the value might be different, or it may not be defined at all. Because Rust is meant to be a safe language, the compiler prevents this kind of undefined behaviour.

So, constantly(n) can’t return a normal function, because the function won’t remember the value of n. It also can’t return a closure, because Rust doesn’t allow us to directly reference a closure’s type.

After some searching, I found a Stack Overflow answer about how to return a closure from a function in Rust, which lead me to a proper implementation of constantly:

fn constantly(n : i64) -> Box<Fn() -> i64> {
  Box::new(move || n)
}

There’s a lot going on here, so I’ll break it down. First, the function signature:

fn constantly( n : i64) -> Box<Fn() -> i64>

This can roughly be translated as: “constantly is a function that takes a 64-bit integer — call it n— and returns a Box containing another function that takes no argument and returns a 64-bit integer.” The main change here is the Box<>.

So what is a box? For our purposes, it’s just a pointer. Box also comes with a static method, Box::new(), that allocates an object on the heap, and returns a reference to that object. For example, the line Box::new(move || n) in our program tells the compiler to allocate move || n on the heap, and return a reference to it. The move keyword, as I understand it, tells the closure (denoted by ||) to capture n by value.

The upshot of all this is that Rust doesn’t support higher-order functions as such — at least not in the general case. The closest you can get is to use function pointers, as you would in C. That said, you can call a Box<Fn> without dereferencing, so you can often ignore the boxing altogether. This might be because the box inherits its function’s call implementation, but I haven’t gotten deep enough into the trait system to say for sure.