"Known size" and closure traits in return parameters

code review
1

Hello, I've been starting with Rust recently and there is something I don't quite understand about return parameters when returning closures. In particular, the following snippet is rejected by the compiler:

fn step<A>(acc: Vec<A>, val: A) -> Vec<A> {
    acc.push(val);
    acc
}

fn filter<A>(pred: impl Fn(A) -> bool) ->  impl FnMut (FnMut (Vec<A>, A) -> Vec<A>) -> FnMut (Vec<A>, A) -> Vec<A> {
    move | step | {
        move | acc, val | {
            if pred(val) {
                return step(acc, val);
            }
            else {
                return acc;
            }
        }
    }
}

because

move | step | {
        ^^^^ doesn't have a size known at compile-time

Could anyone be kind enough to help me fix that? Can it get fixed without Boxing the closures? (Context: I am translating some transducers from a personal Python project)

2

So the thing here is that FnMut is a trait, and you can't have values of type FnMut directly. You can have a MyClosure type that implements the FnMut trait, and functions can say that they accept any type implementing a trait.

Let's ignore the return type for now. Here's are two equivalent ways to write filter (without the return type).

// with impl Trait
fn filter<A>(pred: impl Fn(A) -> bool) {
    ...
}
// with generics
fn filter<A, F>(pred: F)
where
    F: Fn(A) -> bool,
{
    ...
}

The first way of writing this is just a shorthand for the latter method using generics. Since you can't use the trait Fn as its own type, we use generics to duplicate the filter method for every choice of F, and each duplicate will accept some specific concrete type we name F, and we know that F implements the trait described in the bounds.

The question is now: "What happens with the return type?". Because if you try to write it with generics

// doesn't work
fn filter<A, RetF>(pred: impl Fn(A) -> bool) -> RetF
where
    RetF: impl FnMut(Arg) -> Ret,
{
    ...
}

Then we are saying that we duplicate filter for every possible RetF that implements the FnMut trait with those arguments, but that's not really what we want.. We want the specific type of the closure we construct inside the body. For this purpose, Rust provides a feature known as existential types that allow us to do exactly that. It is written as impl Trait like we saw in the argument, but it means something different than when we used it as an argument. So what we really want is this:

fn filter<A>(pred: impl Fn(A) -> bool) -> impl FnMut(Arg) -> Ret {
    ...
}

This tells the compiler that the return type is some specific type that implements the trait, but we give it no more information, and it will figure it out from the body.

But what about the argument to our returned closure? Well we want to be able to give it a closure, but we might want to call it with multiple different closures. So by the arguments above .. we want it to be a generic too? But the generic shouldn't be on filter, because then after it is returned, the argument would still be one specific type, and not be callable with any closure.

To solve this, Rust provides a special type denoted as dyn Trait. When we use the dyn keyword like that, we are referring to a special type known as a trait object, and all values that implement the trait can be turned into the trait object type. That said, trait objects can't be "bare", they have to be behind a pointer of some sort, most commonly a Box.

That makes our argument type written as Box<dyn FnMut (Vec<A>, A) -> Vec<A>>. We also have to use a trait object for the return type — existential types are not allowed in that position.

Finally you will end up with this signature:

fn filter<A>(pred: impl Fn(A) -> bool) ->
    impl FnMut (
        Box<dyn FnMut (Vec<A>, A) -> Vec<A>>
    ) -> Box<dyn FnMut (Vec<A>, A) -> Vec<A>> {
    ...
}

Now you will run into some issues with cloning your A and sharing your predicate among returned closures, but you can fix those with some + 'static and perhaps sharing the predicate with an Rc.

2 Likes
3

Hello, thank you very much for your encompassing answer! Indeed I mentioned Boxing in OP but I didn't recognize that it would be required.
Now, if I write:

fn filter<A>(pred: impl Fn(A) -> bool) ->  impl FnMut (Box<dyn FnMut (Vec<A>, A) -> Vec<A>>) -> Box<dyn FnMut (Vec<A>, A) -> Vec<A>>
{
    Box::new( move | step | {
        Box::new( move | acc, val | {
            if pred(val) {
                return step(acc, val);
            }
            else {
                return acc;
            }
        })
    })
}

, I still run into

Box::new( move | step | {
   |                ^^^^ consider giving this closure parameter a type

so Boxing was not enough to allow for "dynamic" heap-allocation of the closure? I still need to annotate the step argument within the outer closure? I am not sure which concrete type I would have to write there as the whole point was to accept a plurality of possible types there.

4

Your outer closure is returned with impl Trait, not dyn Trait, so you shouldn't box it. It's running into trouble trying to find an impl of FnMut for the type Box<SomeSpecificClosureType>

5

Okay, it's almost fixed, thank you very much for your generosity. It's been a treat to benefit your explanations!

6

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.