How to return an anonymous function/lambda that receives a lambda/function?

Question

It's possible to create a ordered pair (cons in Lisp) using a lambda and a function, as shown in Use of lambda for cons/car/cdr definition in SICP

It also works in Python:

def cons(x,y):
    return lambda m:m(x,y)
def car(z):
    return z(lambda x, y: x)
def cdr(z):
    return z(lambda x, y: y)

When I implement it in Rust, which is a statically-typed language:

fn cons(x: i32, y: i32) -> Box<Fn() -> Fn(i32, i32)> {
    Box::new(move |m| m(x, y));
}

it shows the errors:

error: the type of this value must be known in this context
 --> src/main.rs:2:23
  |
2 |     Box::new(move |m| m(x, y));
  |                       ^^^^^^^

error[E0308]: mismatched types
 --> src/main.rs:1:54
  |
1 |   fn cons(x: i32, y: i32) -> Box<Fn() -> Fn(i32, i32)> {
  |  ______________________________________________________^ starting here...
2 | |     Box::new(move |m| m(x, y));
3 | | }
  | |_^ ...ending here: expected box, found ()
  |
  = note: expected type `Box<std::ops::Fn() -> std::ops::Fn(i32, i32) + 'static + 'static>`
  = note:    found type `()`

How do I define the type of m?

score 4 · Accepted Answer · answered Mar 05 '17 at 11:08

First little mistake: you added a semicolon at the end of your function body. This means that

Box::new(move |m|m(x,y));

is just a statement without side effects, much like 3 + 4;. When you remove the semicolon, you will get a better compiler error, because now the compiler starts to connect your expression type with the return type.

Speaking of which: your return type is wrong, unfortunately. What you want, is to capture the two parameters x and y and return a closure which accepts another closure which is then called with the two parameters. This code works:

fn cons(x: i32, y: i32) ->  Box<Fn(&Fn(i32, i32))> {
    Box::new(move |m| m(x, y))
}

As you can see, the type of the returned closure is: Fn(&Fn(i32, i32)). A closure which accepts another closure as argument. You can use it like this:

let fun = cons(3, 7);
fun(&|x, y| println!("{}", x));

But we have two problems here:

Why the reference &? Closures in Rust are Voldemort types and you can only talk about them in terms of the traits they implement (e.g. the Fn trait). Usually, you have two ways to accept an arbitrary type which implements a trait Foo: with static dispatch and monomorphization (fn bar<T: Foo>(x: T)) or as trait object and with dynamic dispatch (fn bar(x: &Foo)). However, you are already returning a trait object (Box<Fn(...)>) and a trait object can't have generic methods (they can't be monomorphized for various reasons). This means that you need to accept a trait object yourself and since trait objects are unsized, they need to hide behind a reference or something like Box.
The closures don't return anything! Correct, because this again would require monomorphization, because Rust is statically typed. The examples you showed/linked are in dynamically typed language, where things like these are not a problem. In Rust, it's a different story. You can fake dynamic typing in Rust by using Box<Any> or something like that. But this is not really idiomatic and should be avoided. Maybe you really need it, but maybe you also want to incorrectly use patterns from other language in Rust and should instead think in a more rusty way about your problem ;-)

How to return an anonymous function/lambda that receives a lambda/function?

1 Answers1