Closure troubles


#1

I’m trying to write a fairly simple recursive function which applies itself to the left part of an array and the right part, and calls the continuation with the result, like this (the example is just a rather complex way of summing an array very redudantly):

use std::vec::Vec;

fn iterate_segments<F>(nums: &Vec<i32>, start: usize, end: usize, cont: F)
    where F : Fn(i32)
{
    if start + 1 == end {
        cont(nums[start]);
    } else {
        for j in start + 1 .. end {
            iterate_segments(nums, start, j, |op1: i32| {
                iterate_segments(nums, j, end, |op2: i32| {
                    let r = op1 + op2;
                    cont(r);
                });
            });
        }
    }
}

fn main() {
    let nums: Vec<i32> = vec![1i32, 6, 7, 9];

    iterate_segments(&nums, 0, nums.len(), |n: i32| { println!("{}", n); });
}

But I cannot get it to compile. This particular code results in the rather mysterious message “error: reached the recursion limit during monomorphization”. Can anyone explain me how to escape from that? I tried FnMut, but that led to another error, and I don’t see any “mut” here (so it doesn’t make sense to me). FnOnce lead to problems with capture of moved value “cont”.

Thanks in advance.

Edit: in the playground: https://play.rust-lang.org/?gist=a44dced04a7d02ed469c&version=stable


#2

I don’t know if it’s the right solution, but one way to get this code to compile is to get rid of the monophization. Someone will probably explain better than me, but what it means is that iterate_segment is generic and each time it is called, a new implementation is generated (by “monomorphisation”) and there is a limit on the number of times it can be done in a recursion.

It compiles if you change iterate_segments to

fn iterate_segments(nums: &Vec<i32>, start: usize, end: usize, cont: &Fn(i32))

instead of

fn iterate_segments<F>(nums: &Vec<i32>, start: usize, end: usize, cont: F)
    where F : Fn(i32)

(you’ll also have to change the calls to this function, e.g.:

        for j in start + 1 .. end {
            iterate_segments(nums, start, j, &|op1: i32| {
                iterate_segments(nums, j, end, &|op2: i32| {
                    let r = op1 + op2;
                    cont(r);
                });
            });
        }

)


#3

I would like to elaborate that in Rust each closure has a unique type, and it is the reason why new implementations are generated. That is, although |x: i32| x and |x: i32| x + 1 both satisfy the bound Fn(i32) -> i32, their types are different.


#4

First: thanks! That seems to work.

Second: is there information on the difference between |…| { } and &|…| { }? Is is that for the latter “cont” doesn’t need to be copied because it’s a pointer to the continuation rather than the continuation as a value?


#5

Ok, but with my naive eye, I only see three closures, so why would there be a problem? Or is it because for each of the two outermost closures, the inner one creates two new types which changes the type of the |op1:i32| closure, which creates a new type for the inner one, etc.?


#6

iterate_segments is generic over the closure type, and Rust will generate one version per F it’s called with, and for each of them you are calling it again with new closure types, so Rust keeps generating new versions of iterate_segments. Replacing F with &Fn(i32) doesn’t cause such a cycle, because &Fn(i32) is a type on its own. No more need to specialize iterate_segments for each call.


#7

This closures are in a generic function so I think that types of the closures are different for each concrete type of F. And because there is a recursion, you get an infinite family of types, which is really cool, but not very useful :slight_smile:

Actually, the main difference is not here. Consider this snippets:

A)

fn iterate_segments(nums: &Vec<i32>, start: usize, end: usize, cont: &Fn(i32))

B)

fn iterate_segments<F>(nums: &Vec<i32>, start: usize, end: usize, cont: &F)
    where F : Fn(i32)

Note that B also takes cont argument by reference.

B takes any type which implements Fn(i32) and uses static dispatch. A takes a trait object Fn(i32) and uses dynamic dispatch. My explanation is really poor, but there are two chapters in rust book precisely about this things:

https://doc.rust-lang.org/book/trait-objects.html
https://doc.rust-lang.org/book/closures.html


#8

Thanks for all your help. Here’s the program I was working on: an attempt to solve puzzles where you get a few numbers and then have to reach a certain target using only +, -, * and /. There is a slightly weird one, where you have to make 26 out of 1, 6, 7 and 9 in two fundamentally different ways (so excluding symmetry). Rack your brains if you want, or run this: https://play.rust-lang.org/?gist=6ae49ee5f26de20367d5&version=stable

Edit: the goal was of course not to solve that particular puzzle, but rather to do something algorithmically complex in Rust.