High Order Function with Type Parameter


#1
fn f<A: Read, G: Fn(A) -> ()>(g: G, pred: bool) {
  if pred {
    g(File::open("foo").unwrap());
  } else {
    g(Cursor::new(b"foo"));
  }
}

Compile error:

bug.rs:6:7: 6:33 error: mismatched types:
 expected `A`,
    found `std::fs::File`
(expected type parameter,
    found struct `std::fs::File`) [E0308]
bug.rs:6     g(File::open("foo").unwrap());
               ^~~~~~~~~~~~~~~~~~~~~~~~~~
bug.rs:6:7: 6:33 help: run `rustc --explain E0308` to see a detailed explanation
bug.rs:8:7: 8:26 error: mismatched types:
 expected `A`,
    found `std::io::cursor::Cursor<&[u8; 3]>`
(expected type parameter,
    found struct `std::io::cursor::Cursor`) [E0308]
bug.rs:8     g(Cursor::new(b"foo"));
               ^~~~~~~~~~~~~~~~~~~
bug.rs:8:7: 8:26 help: run `rustc --explain E0308` to see a detailed explanation
error: aborting due to 2 previous errors

Why? And how to workaround this?


#2

That generic syntax means that the caller gets to chose the A and G types that it wants to call the function with, not that the body of the function can select whatever A it wants. It’s saying “for every pair of types A which is Read and G which is Fn(A), there exists a function f that does this…”. I don’t know if there’s any way to do what you want directly with the Fn trait. You’d really need to “lower” the A type parameter from the trait itself onto the trait’s method. Something like this will work, for example:

trait Foo {
  fn call<A: Read>(&self, a: A);
}

fn f<G: Foo>(g: G, pred: bool) {
  if pred {
    g.call(File::open("foo").unwrap());
  } else {
    g.call(Cursor::new(b"foo"));
  }
}

#3

To add on to @sfackler’s answer:

The problem with fn f<A: Read, G: Fn(A) -> ()>(...) is that anyone can call f with any A. I could arbitrarily define A to be anything when calling, for instance, it would be perfectly legal to use f::<std::io::Cursor, _>(|cur| cur.set_position(2)), and your function would be forced to provide my function with a Cursor.

In other words, since A is generic, the caller defines A. You have to provide the right A, you can’t just choose one thing which implements Read, because G may be a function which will only accept a Cursor, or a TcpStream, etc.


#4

Got it thanks.

Is there a way to make lambdas with type |A| -> () an instance of Foo?

And in Haskell this problem can be solved using existential type:

{-# LANGUAGE Rank2Types #-}

f :: (forall a. (Num a) => a -> t) -> Bool -> t
f g p = if p then g (1 :: Int) else g (1.1 :: Double)

Is there similar thing in Rust?


#5

We do have higher-ranked trait bounds but they currently only work for lifetimes. If they worked for type parameters you could do something like this:

fn f<G>(g: G) where G: for <A: Read> FnOnce(A) {
    if false {
        g(File::open("foo").unwrap());
    } else {
        g(Cursor::new(b"foo"));
    }
}

However, this fails with a compile error:

error: expected `>` found `A`
where G: for <A: Read> FnOnce(A)
              ^

I don’t know if the closure expansion is actually capable of generating fully generic closures even if this did work. It’s probably on the table of features to implement one day, likely as part of the broader Higher Kinded Types initiative.

Automatically implementing Foo for closures would require the same higher-kinded polymorphism, AFAIK, so that’s not really possible either.

You can get runtime polymorphism with trait objects:

// You only need FnOnce since you don't use the closure more than once.
// And you can omit the `-> ()` the same as you can on functions.
fn f<G: FnOnce(&mut Read)>(g: G, pred: bool) {
    if pred {
        g(&mut File::open("foo").unwrap());
    } else {
        // Notice the argument to `Cursor::new()` changed a bit, 
        // that's because `b"foo"` is actually `&[u8; 3]`, which does not implement `Read`.
        // It won't coerce to `&[u8]` (which does implement `Read`) in this position 
        // so we need to make the conversion explicit.
        g(&mut Cursor::new(&b"foo"[..]));
  }
}

However, this adds overhead due to dynamic dispatch (since the concrete Read impl has to be discovered at runtime). If you’re not worried about being the fastest you can be, this overhead is probably negligible for your application. It’s just something to keep in mind if you run into performance bottlenecks later on.


#6

Thanks for the reply. Unfortunately I cannot pass &mut Read to g because something inside it requires the ownership of the Read.

I think for now requiring G: Foo is the only way working for me.


#7

&mut Read implements Read directly so it can act like an owned value in generic contexts.


#8

I understand that in Rust, all (and only) lambda expressions are closures; and closures are trait types such as Fn.

I understand we can emulate rank-2 (higher ranked) types in a language which doesn’t explicitly support them via forall, by employing a trait with a method for generic parameter A, as explained in an example for Scala.

Compared to that linked Scala example, the example in this thread is not requiring a higher ranked type, because the Read trait lower bound is constant throughout the function f. Also afaics, the example in this thread does not require a higher-kinded type on the trait Fn in order to parameterize the lower bound on the type parameter A of Fn, i.e. requires a trait Fn<A> to be of the type trait Fn<Read>. Higher-kinded types are of the form trait HK<A, B<A>>.

Agreed. The reason the example of this thread won’t compile is not due to a lack of higher-kinded nor higher-ranked types, but rather because afaik the way Rust implements ad hoc polymorphism is it creates a separate instance of each function for each caller that uses a different set of input types, i.e. Rust’s implementation is not a dynamic dispatch of passing in a hidden input argument for the dictionary for the trait implementation of the caller and is instead hard-coding the dictionary in each instance of the function, e.g. is not subclassing nor dynamic inversion-of-control ad hoc polymorphism (where the caller inputs the dictionary). Thus the function f has no way to control the types of Read instance of G it wants unless it specifies them. If f knows all the specific instance of Read it will use, then it can specify them as the lower bound on A instead of Read, except there is the problem that Rust (nor Haskell, nor Scala, nor Kotlin, etc) does not support first-class disjunctions (aka unions) thus we can’t write:

fn f<A: FileHandle | Cursor, G: Fn(A) -> ()>(g: G, pred: bool) {

So thus this is the only way to implement this example in Rust.


Most coveted Rust features
Design patterns for composability with traits (i.e. typeclasses)?
Does rust really need higher kinded types?
How to use a closure as an argument of another closure?
#9

How would a disjunction work here? A is a type parameter, so you could call f::<FileHandle, _>(|_| { /* .. */ }, true). What you want is for G to be a polymorphic function, not f, which is not possible because of monomorphization.


#10

Using an existential type in Haskell will use runtime polymorphism, so it is in effect the same solution as using a trait-object in Rust.

There is another related issue here, and that is you cannot use a generic parameter less generically. For example if we reduce the original code to this:

fn f<A: Read, G: Fn(A) -> ()>(g: G, pred: bool) {
  if pred {
    g(File::open("foo").unwrap());
  } 
}

It still does not work, because we are saying that ‘A’ is a type parameter, which could be any type that implements Read, but at the same time it can only be ‘File’ so it is not generic at all, so even this will not work. Rust complains it expected ‘A’ but found ‘std::fs::File’.

Here’s a solution that works in the current type system:

use std::io::{Read, Cursor};
use std::fs::{File};

fn f<'a, G, H>(g: G, h: H, pred: bool) where G : Fn(File) -> (), H : Fn(Cursor<&'a[u8; 3]>) -> () {
    if pred {
        g(File::open("foo").unwrap());
    } else {
        h(Cursor::new(b"foo"));
    }
}

fn g<A>(mut a : A) -> () where A : Read {
    let mut s : String = String::from("");
    println!("{}", a.read_to_string(&mut s).ok().unwrap());
}

fn main() {
    f(g, g, false);
}

So we have an argument for each use of the function with a different type in f, and then we pass the same function to each of these. This works because the definition of ‘g’ is polymorphic so it can be applied to different types, function arguments are monomorphic so can only be applied to one type.


#11

That should have been a conjunction and it should be using a trait object:

fn f<A: FileHandle ∧ Cursor, G: Fn(&A) -> ()>(g: G, pred: bool) {

So thus that is more restrictive and less generic than it needs to be. Instead just use a trait object:

fn f<A: Read, G: Fn(&A) -> ()>(g: G, pred: bool) {

We would need a conjunction where a function has an input employing a generic with a lower bound of more than one disjoint trait object types. We would need a disjunction when writing the element type of a container populated more than one disjoint trait object types, e.g. Vec<&File ∨ &Cursor>.


#12

Personally I would rather see higher kinded types than intersection and union types. Intersection types start to do strange things when combined with higher kinded types, which requires the introduction of expansion variables into type signatures, and makes unification undecidable (IE type inference and type checking may never terminate). The solution with higher kinded types, which I think someone else gave above would be:

fn f<G>(g : G, pred : bool) where G : for<A : Read> Fn(A) -> ()

This would work as the original poster expected.


#13

Don’t you need some sort of subtyping for disjunction to be really useful - to turn a Vec<&File> to a Vec<&File ∨ &Cursor>?

In any case, your “new” function signature still has the same problem - A is bound with the wrong polarity, and your function can be called as, say,

fn take_a_read(_a: &&[u8]) {}
fn main() {
    f::<&[u8], _>(take_a_read, true)
}

What you want is for f to pick A, rather than for the caller. And for that you need HKT or rank-2 trait bounds.


#14

I think what is wanted is a intersection type like this:

fn f(g : Fn(&File) -> () ∧ Fn(&Cursor) -> ())

The intersection of two functions is a single function that can accept either signature (it is like overloading) as opposed to a union type which would be either. The reason to prefer function intersections can be seen by considering the difference between the following:

fn f(g : Fn(File) -> File ∧ Fn(Cursor) -> Cursor)
fn f(g : Fn(File ∨ Cursor) -> Fn(File ∨ Cursor))

The first guarantees to return the same type of object that you pass, the second does not. Note: they are intersections on types, not traits / type-classes, so ‘Fn’ would need to be a type not a trait. Intersection types do not work well with traits (type-classes) as they are both trying to control overload resolution. As Rust has taken the type-class route to control overloading, adding intersection types would not make sense to me. Higher-kinded-types work nicely with type-classes, so that is the way to go. Union types cause all sorts of problems and are generally unsafe, and Rust has disjoint-union types already (enums) which provide a save sort of union type.

HKT will provide monomorphisation, which you wanted, as does the solution I posted above where you pass the same function twice. Intersection of function types provides an alternative to HKT to do this, but I prefer HKT with traits/type-classes. Union types require (unsafe) runtime polymorphism which is the same as the runtime polymorphism provided by enums.


#15

Afaics yes Vec<&File> is a subtype of Vec<&File ∨ &Cursor>, so thus you then need to enforce a choice of invariant, covariant, and contravariant conditions for type parameters.

f is enforcing a lower bound of Read on A. And the input is a trait object, so both File and Cursor implement the Read trait.

No that shouldn’t compile because [u8] implements Read thus is a subtype of Read, and since g is a covariant input, then A is contravariant when employed in g thus only allowing you to input to g those functions with an A that is a supertype of (or a) Read. You violated the Liskov Substitution Principle. Does Rust allow that?

Note my original version was correct and I should not have changed it from a disjunction to a conjunction. I had forgotten that you were violating LSP.


#16

I can’t find any documentation of that syntax. Only this:

That is, Rust has no notion of type abstraction: there are no higher-ranked (or “forall”) types
abstracted over other types, though higher-ranked types do exist for lifetimes.

Will it work as expected if not being employed for lifetimes?

Can you please elaborate or provide a resource that can explain this in more detail? Is this only applicable when global type inference is required? Are you referring to this?

Could you please show an example? I think you mean only in the case of an of an unbounded generic type?

Well you can use inheritance in a trait to define an tagged intersection, but not an untagged (first-class) intersection. So why does adding untagged traits create an incongruency? Afaics, there is no diamond multiple inheritance problem because Rust doesn’t put implementation in traits.

What problems? They would break Haskell’s global inference. Rust’s enum is a tagged union, not a first-class untagged union.

Not unsafe. The compiler has enforced the invariants of the what runtime types can be. The runtime dispatch enables adhering to those invariants without the boilerplate of having to specialize each parametrized type for each type of (first-class/untagged or tagged Enum) union of types of that can populate the type parameter. Analogously first-class functions enable us to use functions as values and types without having to write boilerplate such as Java’s method pattern for a callback before Java8.

Neither of those with enable you to populate a collection with an extensible union of element types. You seem to be comparing apples to tractors, i.e. even they can both be used to supply food, they don’t solve the same need for food in all the same scenarios.


#17

Dealing with those points one at a time:

  1. The example of HKT does not work in Rust today, as Rust does not have HKT, it is an example of what the syntax could look like, based on the current use of For for universally quantifying lifetimes. The solution where there is a function argument for each use with a different type in the generic function body works with rust as it is now.
  2. I think (1) answered that as well.
  3. HKT and Intersection types are well studied, see: http://www.macs.hw.ac.uk/cs/techreps/docs/files/HW-MACS-TR-0029.pdf but maybe I am focusing too much on type inference, you may like your code littered with type annotations?
  4. I mean that you provide two mechanisms to do the same things, for example a function to accept all readable types is:
fn read<A>(A : a) where A : Read

if File and Cursor implement Read, you could also write

fn read(File \/ Cursor)

And using intersection types you could also write:

fn read (File) -> () /\ (Cursor) -> ()

In the intersection case we care clearly overloading “read” with two implementations which we might write with Traits:

trait MyRead : Read {
    read(&Self); 
}

impl MyRead File {
    read(&Self) { ... }
}

impl MyRead Cursor {
    read(&Self) { ... }
}

So I would rather have a type system with one sound way to do things, rather than multiple alternative ways to do things. I would not want to end up like Scala with an unsound type system full of bugs. http://www.scala-lang.org/blog/2016/02/17/scaling-dot-soundness.html I find the last sentence surprising, type theory isn’t really what I would call surprising, but yes, if you just grab a bunch of shiny stuff and try and bolt it together it won’t be sound, I don’t find that surprising.
5. I refer you to the answer (4), multiple ways to do things is bad, so unless you are suggesting getting rid of traits, Rust doesn’t need another way to do the same thing. see Scala’s problems.
6. As the union is untagged once you have put a value of either type into the variable you cannot ever determine which it was. You are limited to only running functions that can run successfully on either value, without knowing which value is actually there. Think about this for a while, and tell me you have a use for it? As soon as you try and work out what type the value in the union might be you are unsound (because remember its untagged). What functions can you run on a “String / Int”? None right? So maybe I overstated my case, instead I should say: to do anything useful requires writing unsound programs.
7. Sort of, if the compiler can statically prove that the union type has a String in it, then it can simplify it to simply a String, however any generic functions using the union type cannot do anything with it still, apart from pass it to the identity function :slight_smile:
8. To populate a collection with an “extensible union” of element types you want to use a trait object. This is the perfect solution for the your scenario. If you have a “FarmItem” trait and make Apples and Tractors implementations of it, you can then put them both in an array of FarmItem trait objects.


#18

As a bonus, here’s how to do what you wanted originally using traits:

    use std::io::{Read, Cursor};
    use std::fs::{File};
    trait ReadFn {
        fn read<T : Read>(&mut self, T) -> ();
    }
    fn read_test<G>(mut g : G, pred : bool) where G : ReadFn {
        if pred {
            g.read(File::open("foo").unwrap());
        } else {
            g.read(Cursor::new(b"foo"));
        }
    }
    fn main() {
        struct MyFn<'a> {
            buf : &'a mut String
        }
        impl<'a> ReadFn for MyFn<'a> {
            fn read<T : Read>(&mut self, mut a : T) -> () {
                println!("{}", a.read_to_string(self.buf).ok().unwrap());
            }
        }
        let mut s = String::from("");
        read_test(MyFn{buf : &mut s}, false); // passing mutable 'closure' variable
        println!("{}", s);
    }

We use the unit struct ‘MyFn’ as an argument to the generic function to select the trait implementation to use. Instead of a closure you implement ReadFn for as many different unit-structs as you like, so the unit-struct is effectively a type-level name for the function you want to pass. Now you just pass ‘MyFn’ to the generic function and it can apply it to all the different readable types you like in that generic function.

Edit: I actually find this solution quite elegant, and the use of traits to pass polymorphic functions makes me wonder it adding higher-kinded-types is complicating the type system unnecessarily. I would be interested to see any motivating examples for HKT, and see how they look using a trait encoding (but let’s do that in a different topic).


Does rust really need higher kinded types?
Design patterns for composability with traits (i.e. typeclasses)?
#19

I think you mean higher-ranked, not higher-kinded (refer to the quoted linked Scala example):


Does rust really need higher kinded types?
#20

I think you are right, I moved from typing higher-ranked-types to higher-kinded-types without noticing. I don’t think this is limited to rank-2 types, and can handle rank-n polymorphism. I also think you can use the same technique where you might think you need higher-kinded-types, have a look at this implementation of a lazy streaming filter. Does rust really need higher kinded types? if adapter functions are a motivation for HKT you can see we can use the same techniques to do that too.

As far as I can see this satisfies all your original requirements, you can pass closure variables, and it applies polymorphically to the arguments inside the function ‘f’. I also find the Rust and Haskell implementations of this much more readable than the Scala.