Generic function in a struct

help
1

How can I put a generic function (fn pointer or even &dyn Fn) inside a struct without loosing genericity?

So I want the following to compile

fn id<T>(x:T)->T{
    x
}

fn main() {
    let f = Fun{func: id};
    let res1 = (f.func)(2);
    let res2 = (f.func)("hello");
    println!("{res1}, {res2}")
}

how should I define the struct?

defining it as

struct Fun<T> {
    func:  fn(T)->T,
}

does not work

similarly

struct Fun<'a, T> {
    func:  &'a dyn Fn(T)->T,
}

in each case the first function call succeeds but it fixes type parameter T to integer so the following &str call fails.

The struct need not be generic, as the parameter T can be only defined and bound for the function inside the struct.
If I make up a hypothetical syntax, maybe the thing I am looking for is somthing like for<T> fn(T)->T

is there any way to achieve these?

2

The function pointer itself can't be generic like that (nor can be any other type, for that matter). An instantiated, point-able function must exist, so it can't be generic, it already has to be monomorphized. (This is the same reason why trait objects can't have generic methods.)

2 Likes
3

dyn only allows you to have different implementations of the same type, not different implementations of different types.

When the function is called, Rust needs to know at compile time what type it takes and what type it will return. Otherwise it's just impossible to emit machine code to do that.

In other languages such dynamism works, because the function type is not fn(T)->T, but something like fn(Box<dyn Any>)->Box<dyn Any> which is a concrete function type taking and returning runtime-dynamic types.

1 Like
4

Here I distilled my question to its essence.

fn id<T>(x:T)->T {
    x
}

fn main(){
    //let id = id;  (1) //this should be a no-op and should not change the semantics of the program
    let res1 = id(1); // (2)
    let res2 = id("hello"); (3)
    println!("{res1}{res2}")
}

the code above compiles fine, but if you remove the comments it does not.

I understand monomorphization but compiler is smart enough to call one monomorphized version on line (2) but another at line (3) [ if we remove the line (1)]. I do not see any reason why it could not do the same when line (1) is uncommented.

I understand that there is a coercion from a function item to a function pointer in the let binding in line (1). But function call does not require coercion and monomorphization as we can see from the code.

code still does not compile if we replace the line (1) with

let id = |x| {f(x)}; // (4)

in (4) there is only function call no function pointer coercion. (and if you just put line 4 and either (2) or (3) it compiles again)

5

I tried this, but it doesn't work either:

fn id<T>(x:T)->T {
    x
}

fn main(){
    let id: Box<dyn for<T> Fn(T) -> T> = Box::new(id);
    let res1 = id(1);
    let res2 = id("hello");
    println!("{res1}{res2}");
}

(Playground)

Errors:

   Compiling playground v0.0.1 (/playground)
error[E0658]: only lifetime parameters can be used in this context
 --> src/main.rs:6:25
  |
6 |     let id: Box<dyn for<T> Fn(T) -> T> = Box::new(id);
  |                         ^
  |
  = note: see issue #108185 <https://github.com/rust-lang/rust/issues/108185> for more information

For more information about this error, try `rustc --explain E0658`.
error: could not compile `playground` due to previous error
6

Variables in Rust must have a single concrete type, even when that type is inferred and not explicitly specified. Anything with an unbound type parameter, like fn id<T>, is more properly a type constructor and cannot be stored in a variable. So, in the line let id = id you're asking the compiler to infer a single concrete type to fill in the blank.

In other words, it's impossible to store fn(T)->T in a variable; you have to pick either fn(i32)->i32 or fn(&str)->&str as the type; whichever you choose, there is a type mismatch in one of the following calls. Without the declaration, however, the compiler is calling two different (but related) functions, id::<i32>() and id::<&str>().

6 Likes
7

Arguably, let id = id could work, if the type of id was not generic but the implementation of the Fn* traits was. For example something like this

I think there's probably a reason for this behaviour (something something early vs late bounds?) but I'm not sure what it is.

3 Likes
8

Note that this still doesn't solve the problem, it merely shifts it to the call method of the Fn* traits. The equivalent of OP's problem would be desugaring the call and assigning the call method itself to a variable — which once again wouldn't work for the same reasons as described above.

The general problem is called let polymorphism.

3 Likes
9

You can often get around this by declaring a trait yourself, something like

trait IdFn {
    fn id<T>(x: T) -> T;
}

struct PrintsId;

impl IdFn for PrintsId {
    fn id<T>(x: T) -> T {
        dbg!(x)
    }
}

and then you can store PrintsId (since it's a specific type).

10

I do not see how is this a workaround.

Let us say want to implement a pretty printer for say html. all the nodes implement a trait HtmlNode I want to expose a function print_html(transform: fn(T: HtmlNode)->String) with the intention that I will walk the html tree and apply the transform function to each of the nodes. Given that there are different types that implement HtmlNode say formElem divElem etc. the transform function has to be generic.

But as far as no one can provide for one because any function value that can be passed to a function has to me monomorphic.

(Assume using an enum instead of a trait HtmlNode and have the function transform(f: HtmlNode -> String) is not feasible we want to be future compatible so that if html spec includes new node types we dont want to break already existing transform functions)

11

If you need it to literally be a function pointer you are correct, it can't be generic, but if you could change your code to use a custom trait you can make this work:

trait Transform {
    fn transform<T: HtmlNode>(x: T) -> String;
}

print_html(transform: impl Transform)
12

Is this also why the following approach won't work?

fn id<T>(x:T)->T {
    x
}

struct St<T> {
    func: Box<dyn Fn(T) -> T>,
}

trait Tr {
    type Type;
    fn into_type(self) -> St<Self::Type>;
}

impl<T> Tr for St<T> {
    type Type = T;
    fn into_type(self) -> Self {
        self
    }
}


fn main(){
    let id: Box<dyn Tr> = Box::new(St { func: Box::new(id) });
}

(Playground)

Errors:

   Compiling playground v0.0.1 (/playground)
error[E0191]: the value of the associated type `Type` (from trait `Tr`) must be specified
  --> src/main.rs:23:21
   |
10 |     type Type;
   |     --------- `Type` defined here
...
23 |     let id: Box<dyn Tr> = Box::new(St { func: Box::new(id) });
   |                     ^^ help: specify the associated type: `Tr<Type = Type>`

For more information about this error, try `rustc --explain E0191`.
error: could not compile `playground` due to previous error
13

Type parameters on function types are early bound, and as of yet Rust doesn't have any types which are higher-ranked over anything but lifetimes. So when you assign id = id, you're really assigning id = id::<_>, and in this case the compiler infers that to be id = id::<i32>. [1] (The syntax is valid, you can try them out and see how it changes the errors.)

It works similarly for structs.

    let none = None;
    let mut res1 = Some(1);
    let mut res2 = Some("hello"); 
    
    res1 = none;
    res2 = none; // Error, found Option<{integer}>

Here, None is really None::<_> and the compiler infers that must be the same type as res1 due to the assignment, just like what happened with id.

If id<T> was late-bound in T, then it would act how you thought it would.

You can read more about how things work and explorations of how they could evolve in this RFC draft. In particular,

There's no coercion to a function pointer, it's still a function type. This is relevant because, for example, function pointers can't (yet) carry lifetime constraints. Example of the constraints holding. For this reason, lifetimes with constraints are early bound, so you can't get a higher-ranked function pointer out of them. (There are still related holes in the compiler around higher-rankedness though.)

Closures can't be higher-ranked over types (yet).

  1. Actually it errors out before it's decided anything more than "some integer type", but you get the idea. It's looking for a single type for T. ↩ī¸Ž

3 Likes
14

Yes, basically.

1 Like
15

First of all, thank you for your response, and the links that you provided, they are quite interesting read.

So far all the responses in this post agree that a local variable cannot hold a polymorphic value, and that nominally answers the original question to effect that as Rust stands today you cannot have a polymorphic value inside a struct. So, if it makes any difference I can mark any one of the responses as a solution and let the discussion close.

However, the underlying reasons for this limitation can be a further topic of interest. Your pointers to issue of early binding vs late binding are great examples.

In your response there is a term that I do not understand which is " a type is higher-ranked over (type/lifetime) " . So you say:

What about fn id<T>(x:T)->T {x}. what about its type is it "higher ranked"?

There is conventional usage of "higher ranked/kinded" that classifies for example Vec<u8> as not higher ranked but Vec itself as "higher ranked/kinded" and you are right that rust does not have bare Vec as a type. But what about (now I am making syntax that does not exist) <T>Vec<T>. This is not bare Vec and yes in Rust as it stands today you cannot have such a value bound to a local variable. But my intuition tells me that it has nothing to with the issue of "higher ranked/kinded" issue here because if anything <T>Vec<T> is not higher kinded at all.

Now you can say I make up syntax and talk about weird hypotheticals, but we have that syntax available for functions fn <T> (x:T) ->T (am I wrong?[not rhetorical I am seriously asking it]) , is this type "higher ranked/kinded"

So, my intuition tells me that "higher ranked/kinded" thing is not the real issue here. And late bound / early bound might be the real underlying issue and again thanks for pointing those out.

16

No, as that's not a type; it's a type constructor, like Vec<T>. The syntax is even the same, when it comes to type parameters. (For lifetime parameters, on functions the lifetime is only early bound when it's part of some bound, in contrast with just declared.)

Here's some syntax for the higher ranked types which have names today:

for<'a> fn(&'a str)
// same thing
fn(&str)

for<'a> dyn Fn(&'a str)
// Same thing
dyn Fn(&str)

// No elided shorthand for this one
for<'a> dyn Trait<'a>

If Rust gains the ability for those particular types, it will probably be for<T>.

The speculation in the links is that the syntax could be fn foo(_: impl Trait) for function declarations/types (that's a breaking change since the syntax is stable with the early bound meaning today, but they might try to get away with it anyway). It would be analogous to how fn foo(_: &str) is shorthand for the late bound fn foo<'a>(_: &'a str).

17

I think I now see how our terminology differ. I would call Vec the type constructor and also a higher kinded type awaiting a type parameter so Vec<u8>, Vec<u16> are types that result from applying type constructor Vec to u8 and u16 respectively. If we had the syntax for<T>Vec<T> I would not call it a type constructor because the type is applied it does not accept any more type parameters there is no such thing as for<T>Vec<T><X>

Similarly I would call fn (_)-> _ a type constructor and a higher kinded type awaiting two type parameters to give us a type, and fn(u8)->u16 is a type that is the application of u8 and u16 to the type constru or fn (_) -> _. so that fn (_) -> _ <u8, u16> == fn(u8)->u16

But curicially I would expect, fn <T> (T)->T to be not a type constructor but a type in particular a generic polymorphic type. So, maybe you what you call higher ranked types are what I call generic polymorphic types, but in either way they are not type constructors or higher kinded(in the usual sense).

But putting the terminological issue aside, it seems that you are right, Rust function types are not polymorphic or generic as I construe them. So I was wrong to think that the type of id function is for<T> fn(T)->T but it is just fn (_)->_ so the <T> in Rust's notation has nothing to do with quantification but just an introduction of a place holder. Interesting!!!

18

I have no formal experience with HKTs so it is quite possible my terminology is a bit off in some way.

You may enjoy this series of blog posts that accompanied the Generic Associated Type (GAT) RFC (what the blog calls an Associated Type Constructor). It explores the concept of what a HKT in Rust might look like.

1 Like
19

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.