错误:实例化`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 typemain#8
. - 1st instantiation of
foo
, inmain
,foo<[main#8]>
. - 2nd closure, in
foo
, let's name the type{foo<[main#8]>}#3
. - 2nd instantiation of
foo
, infoo
,foo<[{foo<[main#8]>}#3]>
. - 3rd closure, in
foo
, let's name type{foo<[{foo<[main#8]>}#3]>}#3
. - 3rd instantiation of
foo
, infoo
,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屋!