Why can't I pass around a generic function if I specify the right `Fn` bounds?

Question

I was answering someone else's question about trying to name the type of, and pass around, a generic function, and I tried writing this code which seems like it's in the spirit of Rust's types and traits:

use std::fmt::Display;
fn generic_fn<A: Display>(x: A) -> String { format!("→{}←", x) }

fn use_twice<F>(f: F) -> String
where
    F: Fn(i32) -> String,
    F: Fn(f32) -> String,
{
    f(1) + &f(2.0)
}

fn main() {
    dbg!(use_twice(generic_fn));
}

However, it fails to compile (on stable Rust 1.52.0):

error[E0631]: type mismatch in function arguments
  --> src/main.rs:13:15
   |
1  | fn generic_fn<A>(x: A) -> A { x }
   | --------------------------- found signature of `fn(i32) -> _`
2  | 
3  | fn use_twice<F>(f: F)
   |    --------- required by a bound in this
...
6  |     F: Fn(f32) -> f32,
   |        -------------- required by this bound in `use_twice`
...
13 |     use_twice(generic_fn);
   |               ^^^^^^^^^^ expected signature of `fn(f32) -> _`

I understand that this means the compiler is requiring the fn item generic_fn to be coerced to a function pointer (the partially specified type fn(f32) -> _). But why? I've heard that fn items have unique zero-sized types — why can't use_twice's parameter f accept that type? Would it cause some trouble in compiling a different program (e.g. type inference failures) if Rust accepted this code? Is this just something that hasn't been implemented yet?

I know it's not a logical impossibility, because if I write my own trait instead of using Fn, then I can explicitly define a generic function that can be passed as a value:

trait PolyFn1<A> {
    type Output;
    fn apply(&self, x: A) -> Self::Output;
}

use std::fmt::Display;
struct GenericFn;
impl<A: Display> PolyFn1<A> for GenericFn {
    type Output = String;
    fn apply(&self, x: A) -> String { format!("→{}←", x) }
}

fn use_twice<F>(f: F) -> String
where
    F: PolyFn1<i32, Output=String>,
    F: PolyFn1<f32, Output=String>,
{
    f.apply(1) + &f.apply(2.0)
}

fn main() {
    dbg!(use_twice(GenericFn));
}

[src/main.rs:22] use_twice(GenericFn) = "→1←→2←"

Using unstable Rust features, I can even implement Fn this way:

#![feature(fn_traits)]
#![feature(unboxed_closures)]
use std::fmt::Display;

struct GenericFn;
impl<A: Display> FnOnce<(A,)> for GenericFn {
    type Output = String;
    extern "rust-call" fn call_once(self, args: (A,)) -> String {
        self.call(args)
    }
}
impl<A: Display> FnMut<(A,)> for GenericFn {
    extern "rust-call" fn call_mut(&mut self, args: (A,)) -> String {
        self.call(args)
    }
}
impl<A: Display> Fn<(A,)> for GenericFn {
    extern "rust-call" fn call(&self, args: (A,)) -> String {
        format!("→{}←", args.0)
    }
}

fn use_twice<F>(f: F) -> String
where
    F: Fn(i32) -> String,
    F: Fn(f32) -> String,
{
    f(1) + &f(2.0)
}

fn main() {
    dbg!(use_twice(GenericFn));
}

Given this, I can restate my question as: why don't Rust's normal function items work like this? Why do they have this seemingly avoidable restriction?

Answer 1

My question is perhaps: why doesn't the concrete type of generic_fn offer this?

Because there's no such thing as "the concrete type of generic_fn". When you write

use_twice(generic_fn)

it's really

use_twice(generic_fn::<Something>)

where Something is inferred by the compiler. But if Something is i32, then generic_fn::<i32> doesn't implement Fn(f32) -> String and similarly generic_fn::<f32> doesn't implement Fn(i32) -> String. So there's no Something that would work.

Maybe

where
    F: for<A> Fn(A) -> String,

would work, but that's not supported (yet?).

In the working case you just pass GenericFn and there's no type parameter to infer there. It needs to be inferred in f.apply(1) and f.apply(2.0), but those are two different places and there's no problem having different type parameters there.

Answer 2

What you're wanting is something called Higher Kinded Types (or their equivalent for functions).

To see what this means, let's first take a look at another example (which does not compile):

trait Foo {
    type Collection;
    fn make_collection<T>(&self) -> Collection<T>;
}

In theory I'd want to be generic over the kind of collection, supporting both Vec and HashSet, and anything else, however we can't do that. What we'd need is a higher kinded type (in this case it's called a generic associated type): Vec. No, not Vec<T>, Vec. We could say that Vec is a "constructor for a type" which takes in as a parameter some type T and spits out another type Vec.

Note that whenever this feature lands, it'd actually look like this (and hence why in this case it'd be called a Generic Associated Type (GAT)):

trait Foo {
    type Collection<T>: FromIterator<T>;
    fn make_collection<T>(&self) -> Collection<T>;
}

Moving out of type land into function land, we can see it's the same situation as you had:

You want a type that's generic over another type... otherwise called a higher kinded type, however we're talking in terms of functions. Function items have their parameters and return types baked directly into their type.

I won't explain what function items are in this answer, but note that the reasoning applies the same to function pointers: the very type of the function (in this case F) encodes the inputs and outputs.

This is why turbofish exists* and feels kind of weird when addressing functions:

foo::<u8>(0u8)

Could be rewritten as

(foo::<u8>)(0u8)

And hence if we had fn(u8) { foo } (in pseudocode for fn items) as F, it'd become pretty clear where the issue is: the only logical Fn trait for this to implement is Fn(u8). We can't get an HKT.

---

This feature, however, has not been implemented yet, and so you'd be better off just passing it in twice:

use std::fmt::Display;
fn generic_fn<A: Display>(x: A) -> String { format!("→{}←", x) }

fn use_twice<F1, F2>(f_i32: F1, f_f32: F2) -> String
where
    F1: Fn(i32) -> String,
    F2: Fn(f32) -> String,
{
    f(1) + &f(2.0)
}

fn main() {
    dbg!(use_twice(generic_fn, generic_fn));
}

---

• *: I have no proof this is why turbofish for functions exists, but it makes sense.

Answer 3

I think the answer lies in the struct GenericFn NOT being a generic type.

A generic type provides a “recipe” that the compiler uses to construct an actual concrete type that can than be used.

A generic struct Foo<A> that is used as Foo<Bar> will be treated by the compiler as a concrete, new, and distinct type. Think of it as the compiler creating FooBar (the compiler doesn’t really create a name like this, but it’s nicer to see). If you used Foo<Baz>, than it would be treated as FooBaz, a type that is separate from FooBar. This is called monomorphization, and is what allows generic types to be zero-cost, because it compiles down to the same thing a creating a new distinct type.

A generic function is pretty much the same thing, it creates a distinct fonction pointer for each different type it is generalized over. foo<bar> (where foo is fn foo<A>(x: A) -> A will give out a pointer, let’s say 1, to a distinct function of type fn(bar) -> bar. Note that this type is distinct but not unique: identity<bar> would give a different pointer, but of the same type. foo<baz> will give a different pointer, say 2, of type fn(baz) -> baz.

Now, a function that wants a type that has both the trait Fn(bar) -> bar and Fn(baz) -> baz, well a function pointer will not cut it, because it only fulfills one concrete implementation, because it points to only one function: pointer 1 isfn(bar) -> bar and that type does not implement Fn(baz) -> baz, and vice versa for 2. You would have to pass two different function pointers, which you do not do.

Your GenericFn works because the concrete type actually implements both PolyFn1<i32> AND PolyFn2<f32>, allowing to pass only one type.

Answer 4

The issue here is that the types are indeed incompatible. You are passing a single function to use_twice and that function needs to have a well-defined type, so there is no way that it can handle

    F: Fn(i32) -> String,
    F: Fn(f32) -> String,

because a single function can't have two different types of arguments it receives. I'm assuming you were hoping it would automatically apply the template twice while still having a single function, but that is not how Rust works.

So revisiting that error

error[E0631]: type mismatch in function arguments
  --> src/main.rs:13:15
   |
1  | fn generic_fn<A>(x: A) -> A { x }
   | --------------------------- found signature of `fn(i32) -> _`
2  | 
3  | fn use_twice<F>(f: F)
   |    --------- required by a bound in this
...
6  |     F: Fn(f32) -> f32,
   |        -------------- required by this bound in `use_twice`
...
13 |     use_twice(generic_fn);
   |               ^^^^^^^^^^ expected signature of `fn(f32) -> _`

It says that it used generic_fn::<i32> and tried to pass that to use_twice, but that is not allowed because generic_fn::<i32> does not pass Fn(f32) -> f32.

So fundamentally your function argument bounds aren't workable and your design needs to change.