错误：实例化`func ::< [closure]>`时达到了递归限制。 [英] Error: reached the recursion limit while instantiating `func::<[closure]>`

问题描述

我正在尝试测试二进制搜索树是否有效：

I am trying to test if a binary search tree is valid:

use std::{cell::RefCell, rc::Rc};

pub struct TreeNode {
    val: i32,
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>,
}

pub fn is_valid_bst(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
    preorder_traverse(root.as_ref(), |_| true)
}

fn preorder_traverse<F: Fn(i32) -> bool>(root: Option<&Rc<RefCell<TreeNode>>>, predict: F) -> bool {
    if let Some(node) = root {
        let root_val = root.as_ref().unwrap().borrow().val;
        if !predict(root_val) {
            return false;
        }
        preorder_traverse(node.borrow().left.as_ref(), |v| v < root_val)
            && preorder_traverse(node.borrow().right.as_ref(), |v| v > root_val)
    } else {
        true
    }
}

（游乐场）：

此代码会触发以下错误消息，这似乎是无意义的对我来说：

This code triggers the following error message and that seems non-sense to me:

error: reached the recursion limit while instantiating `preorder_traverse::<[closure@src/lib.rs:19:56: 19:72 root_val:&i32]>`
  --> src/lib.rs:13:1
   |
13 | / fn preorder_traverse<F: Fn(i32) -> bool>(root: Option<&Rc<RefCell<TreeNode>>>, predict: F) -> bool {
14 | |     if let Some(node) = root {
15 | |         let root_val = root.as_ref().unwrap().borrow().val;
16 | |         if !predict(root_val) {
...  |
23 | |     }
24 | | }
   | |_^

我发现一个可能相关的Rust问题，但它似乎已经过时了，我也无法很好地理解原始问题中引用的消息。

I've found a potentially related Rust issue, but it seems outdated and I cannot understand the quoted message in the original issue well.

• 什么达到了递归限制？


• 如果我想将谓词逻辑封装在闭包中或还有什么？

此代码中用于验证二进制搜索树的算法不正确，但我仍然认为原始代码应该编译。

The algorithm to validate binary search tree in this code is not correct, but I still think the original code should compile.

推荐答案

@Lukas Kalbertodt提供了一个更简单的示例，我

@Lukas Kalbertodt provides a simpler example, which I'll use as a basis for the explanation:

fn foo<F: Fn()>(x: bool, _: F) {
    if x {
        foo(false, || {}) // line 3
    }
}

fn main() {
    foo(true, || {}); // line 8
}

这里的重点是每个闭包都有唯一的类型，所以让我们实例化该程序：

The important point here is that each closure has a unique type, so let's instantiate this program:

• 第一个闭包，在 main 中，让我们命名类型 main＃8 。


• foo 的第一个实例化，在 main ， foo< [main＃8]> 。


• 第二次关闭，在 foo 中，我们将类型命名为 {foo< [main＃8]>}＃3 。


• foo 的第二个实例，在 foo ， foo< ; [{foo< [main＃8]>}＃3]> 。


• 第三个闭包，位于 foo ，让我们键入 {foo< [{foo< [main＃8]>}＃3]>}＃3 。


• foo 的第三次实例化，在 foo ， foo< [ {foo< [{foo< [main＃8]>}＃3]>}＃3]> 。


• ...
  

• 1st closure, in main, let's name the type main#8.
• 1st instantiation of foo, in main, foo<[main#8]>.
• 2nd closure, in foo, let's name the type {foo<[main#8]>}#3.
• 2nd instantiation of foo, in foo, foo<[{foo<[main#8]>}#3]>.
• 3rd closure, in foo, let's name type {foo<[{foo<[main#8]>}#3]>}#3.
• 3rd instantiation of foo, in foo, foo<[{foo<[{foo<[main#8]>}#3]>}#3]>.
• ...

每个新的 foo 实例化都会创建一个新的闭包类型，每个新的闭包类型cr吃了 foo 的新实例，这是没有基本情况的递归：堆栈溢出。

Each new instantiation of foo creates a new closure type, each new closure type creates a new instantiation of foo, this is a recursion without a base case: stack overflow.

可以通过递归调用 preorder_traverse ：

• 要么使用类型擦除，尽管有运行时开销，


• ，或者只是使用单独的内部函数进行递归，因为独立于 F 。

• either using type erasure, although there's a runtime overhead,
• or simply by using a separate inner function for recursion, since it's independent of F.

示例：

fn preorder_traverse_impl(
    root: Option<&Rc<RefCell<TreeNode>>>,
    parent_value: i32,
    predict: fn(i32, i32) -> bool
)
    -> bool
{
    if let Some(node) = root {
        let root_val = root.as_ref().unwrap().borrow().val;
        if !predict(root_val, parent_value) {
            return false;
        }
        preorder_traverse_impl(node.borrow().left.as_ref(), root_val, lessThan)
            && preorder_traverse_impl(node.borrow().right.as_ref(), root_val, greaterThan)
    } else {
        true
    }
}

fn preorder_traverse<F: Fn(i32) -> bool>(root: Option<&Rc<RefCell<TreeNode>>>, predict: F) -> bool {
    if let Some(node) = root {
        let root_val = root.as_ref().unwrap().borrow().val;
        if !predict(root_val) {
            return false;
        }
        preorder_traverse_impl(node.borrow().left.as_ref(), root_val, lessThan)
            && preorder_traverse_impl(node.borrow().right.as_ref(), root_val, greaterThan)
    } else {
        true
    }
}

每晚还可以创建谓词类型并为其实现 Fn （ LessThan< i32> 和 GreaterThan< i32> ）。

On nightly you could also create a predicate type and implement Fn for it (LessThan<i32> and GreaterThan<i32>).

这篇关于错误：实例化`func ::< [closure]>`时达到了递归限制。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！