Higher-order functions: twice


#1

twice is a higher-order function for applying a given function f to an argument twice: it returns a new function which, given an x, returns f(f(x)):

fn main() {
    let succ = |x: i32| x + 1;
    fn twice<T, F: 'static + Fn(T)->T>(f: F) -> Box<Fn(T)->T> {
      Box::new(move |x: T| f(f(x)))};

    println!("succ(0) = {}", succ(0));
    println!("twice(succ)(0) = {}", twice(succ)(0));
//  println!("twice(twice)(succ)(0) = {}", twice(twice)(succ)(0));
}

The first two examples work correctly, but the third one, if uncommented, causes a compile error:

<anon>:9:48: 9:53 error: the trait `core::ops::Fn<(_,)>` is not implemented for the type `Box<core::ops::Fn(_) -> _>` [E0277]
<anon>:9   println!("twice(twice)(succ)(0) = {}", twice(twice)(succ)(0));
                                                    ^~~~~

Is there a way to redefine twice so it can handle this? Here’s a link to this same code in the Rust Playground.

Paul McJones


#2

F is specified as a function that takes and returns the same type, but twice returns a different box type, so it can’t be F itself.


#3

If it took a boxed closure, it would work

fn twice<T: 'static>(f: Box<Fn(T) -> T>) -> Box<Fn(T) -> T> {
    Box::new(move |x| f(f(x)))
}

https://is.gd/ye8uLU


#4

But splicing in another call on _twice generates new error messages: Rust playground:

`<anon>:8:48: 8:54 error: type mismatch: the type `fn(Box<core::ops::Fn(_) -> _>) -> Box<core::ops::Fn(_) -> _> {twice}` implements the trait `core::ops::Fn<(Box<core::ops::Fn(_) -> _>,)>`, but the trait `core::ops::Fn<(_,)>` is required (cyclic type of infinite size) [E0281]
<anon>:8     println!("Hello, world! {}", twice(_twice)(_twice)(succ)(0));

`
I was hoping to find something that would work for an arbitrary T to T function, like this Haskell example:

λ let twice f x = f(f(x)) in twice(twice)(twice)(twice)(succ)(0)
65536
:: (Enum t, Num t) => t

#5

You need to construct a new boxed function each time you pass it with Box::new(twice).

https://is.gd/Bi0Ih7

You can’t pass a boxed function to itself in Rust because the monomorphized type is not computable (Rust is strict, not lazy). I also don’t think it works with Rust’s ownership semantics, but the compiler doesn’t even get there so that’s not as important.


#6

Why is this a monomorphisation issue? C++ templates can monomorphise functions like twice, so it has nothing to do with strict vs lazy, and is not a monomorphisation issue. What is the real problem here?


#7

Probably this has to do with the fact that C++'s template instantiation is not typesafe. What is the type of _twice(_twice) with all of the type parameters resolved?

You start out as (T -> T) -> (T -> T), but then T needs to be resolved, and T is (T -> T) -> (T -> T), so its (((T -> T) -> (T -> T)) -> ((T -> T) -> (T -> T))) -> (((T -> T) -> (T -> T)) -> ((T -> T) -> (T -> T))) and so on.

Laziness was the wrong distinction. Haskell can do this because it allows types to be recursively defined in general, like List t = nil | t :: List t. I don’t think this has to do with lazy evaluation at all.


#8

I don’t see that as a problem, its only a problem with type inference, which we are not doing here. The type is always (T -> T) -> (T -> T).

There is no issue with soundness, as you can monomorphise this, so the type system is rejecting something it should accept. It is not a type system issue, as Haskell shows we can resolve the types (and Haskell does not allow recursive types). So it looks like a simple case of the type system being overly restrictive.

The list example is a different kind of recursion, the list example is iso-recursive, whereas the ‘T->T’ recursion you were implying is equi-recursive. Haskell does not allow equi-recursive types either.

twice :: (T -> T) -> T -> T
twice(twice) :: (T -> T) -> T -> T
twice(twice(twice)) :: (T -> T) -> T -> T
etc...

Edit: I think I see that part of the problem is that you cannot pass a generic function as an argument. Maybe that is what you were saying but I failed to understand it.


#9

Remember that twice here is not exactly a function but a trait object (which is like an existential type) - the trait just happens to be a trait that all functions implement. I suspect this is the actual cause of the difference between Rust and Haskell.


#10

I believe C++ “Concepts” which provide typing for templates and are an equivalent feature to type-classes and traits will allow this, and of course type-classes are implemented by full monomorphisation, so there is something odd going on.


#11

This is some simpler code that would have the same problem (if typeof were implemented yet):

struct Foo<T>(T);

let foo: Foo<typeof(foo)>;

As I said in the previous post, a Box<Fn(T) -> T> is an existential, and the T you are passing to its type parameter is the type of itself. It cannot be fully monomorphized. In Haskell each instance of twice in twice twice twice succ 0 is parameterized by a different type, but the code that didn’t work here was passing a single instance to itself.

I don’t know anything about C++ concepts and I know very little about how Haskell is actually implemented. My impression was that type parameters are not always monomorphized by GHC.


#12

This is true, because Haskell uses universally quantified types not all functions can be monomorphised (due to things like polymorphic recursion). However C++ templates are fully monomorphised and can implement this kind of thing by taking and returning function-objects.

I don’t think this should be using a ‘Box’ or existential types, it should not need it. The C++ version is not using any runtime polymorphism as that would require using virtual functions. So it is possible to fully monomorphise this without existentials, but for some reason rust does not allow it.

Maybe this would be helped by being able to return trait objects? Any idea when (if) that will be getting into nightly?


#13

A Box<Trait> is a trait object, I think you’re referring to the impl Trait proposals, which are either inference or abstraction depending on the proposal. Those would allow you to return an unboxed function, which should allow something like this to just work (no instantiating a boxed closure at all):

fn twice<F: Fn(T) -> T, T: 'static>(f: F) -> type Fn(T) -> T {
    |x| f(f(x))
}

twice(twice)(twice)(twice)(twice)


#14

Yes, thats what is needed for this, any idea how that is getting on?


#15

:slight_smile:


#16

That’s looking good, what is the easiest way to pull that branch?


#17

If you used impl Trait, wouldn’t you be back to the original problem that the input F and the abstract output are not the same type? i.e. twice wouldn’t be Fn(T) -> T, so it couldn’t be used on itself.


#18

Damn, of course, you are right.

The issue here is just that Rust’s closures have an anonymous type. I don’t think you’ll ever be able to do this without instantiating separate trait objects each time.


#19

In the above sample, isn’t twice a top level definition and therefor polymorphic in type T? And as above:

twice :: (T -> T) -> (T -> T)
twice(twice) :: (T -> T) -> (T - T)
twice(twice(twice) :: (T -> T) -> (T - T)

So it always takes and Fn(T) -> T and returns an Fn(T) -> T


#20

Fn(T) -> T isn’t a type, its a trait. Closures each have a unique anonymous type.