递归

以简洁、栈安全和高效的方式处理递归数据结构的工具。

该crate提供了将递归的机制与递归的逻辑分离的抽象。这与迭代器将迭代的机制与迭代的逻辑分离的方式类似，使我们能够从以下内容

let mut n = 0;
while n < prices.len() {
    print!("{}", prices[n]);
    n += 1;
}

变为以下内容

for n in prices.iter() {
    print!("{}", n)
}

第二个示例更简洁，更少样板代码，更容易使用。该crate旨在为处理递归数据结构提供类似工具。

以下是其工作原理：Expr

在这些示例中，我们将使用一个简单的递归数据结构 - 支持一些数学运算的表达式语言。

pub enum Expr {
    Add(Box<Expr>, Box<Expr>),
    Sub(Box<Expr>, Box<Expr>),
    Mul(Box<Expr>, Box<Expr>),
    LiteralInt(i64),
}

为了处理这个Expr类型，我们将定义一个帧类型ExprFrame<A>。它与Expr完全相同，只是递归自引用Box<Self>被替换为A。这可能会有些令人困惑，但这个习惯用法可以解锁很多潜力（表现力、栈安全性等）。你可以将ExprFrame<A>视为表示递归算法中的一个单个栈帧。

pub enum ExprFrame<A> {
    Add(A, A),
    Sub(A, A),
    Mul(A, A),
    LiteralInt(i64),
}

现在我们只需要一些机械的样板代码：为ExprFrame定义MappableFrame，以及为Expr定义Expandable和Collapsible。我现在将省略它，但你可以在上述特质的文档中阅读它们的功能以及如何实现它们。

将表达式折叠为值

以下是使用这种习惯用法评估 Expr 的方法，通过函数 ExprFrame<i64> -> i64 逐帧折叠

fn eval(e: &Expr) -> i64 {
    e.collapse_frames(|frame| match frame {
        ExprFrame::Add(a, b) => a + b,
        ExprFrame::Sub(a, b) => a - b,
        ExprFrame::Mul(a, b) => a * b,
        ExprFrame::LiteralInt(x) => x,
    })
}

let expr = multiply(subtract(literal(1), literal(2)), literal(3));
assert_eq!(eval(&expr), -3);

这是一个可视化 collapse_frames 操作的 GIF

可能出错的函数

此时，你可能已经注意到我们省略了除法，因为除以零是未定义的。许多现实世界的算法也必须处理可能出错的操作，例如这个。这就是为什么这个 crate 也提供了使用可能出错的函数（在这种情况下）ExprFrame<i64> -> Result<i64, Err> 来折叠和展开递归数据结构的工具。

fn try_eval(e: &Expr) -> Result<i64, &str> {
    e.try_collapse_frames(|frame| match frame {
                ExprFrame::Add(a, b) => Ok(a + b),
                ExprFrame::Sub(a, b) => Ok(a - b),
                ExprFrame::Mul(a, b) => Ok(a * b),
                ExprFrame::Div(a, b) =>
                    if b == 0 { Err("cannot divide by zero")} else {Ok(a / b)},
                ExprFrame::LiteralInt(x) => Ok(x),
    })
}

let valid_expr = multiply(subtract(literal(1), literal(2)), literal(3));
let invalid_expr = divide(literal(2), literal(0));

assert_eq!(try_eval(&valid_expr), Ok(-3));
assert_eq!(try_eval(&invalid_expr), Err("cannot divide by zero"));

这是一个可视化 try_collapse_frames 对 valid_expr 操作的 GIF

这是一个可视化 try_collapse_frames 对 invalid_expr 操作的 GIF

从种子值展开表达式

以下是如何从种子值展开简单 Expr 的示例

fn build_expr(depth: usize) -> Expr {
    Expr::expand_frames(depth, |depth| {
        if depth > 0 {
            ExprFrame::Add(depth - 1, depth - 1)
        } else {
            ExprFrame::LiteralInt(1)
        }
    })
}

let expected = add(add(literal(1), literal(1)), add(literal(1), literal(1)));

assert_eq!(expected, build_expr(2));

这是一个可视化 `expand_frames`` 操作的 GIF

其他错误

本文档中的所有 GIF 都是使用我 recursion-visualize crate 中的工具生成的，通过 examples/expr.rs。

如果你熟悉 Haskell，你可能已经注意到这个 crate 大量使用了递归方案的习惯用法。我为使用这些习惯用法的 trait 命名时考虑了可读性，但你可以自由地将 MappableFrame 读取为 Functor，将 Expandable/Collapsible 读取为 Corecursive/Recursive。如果你不熟悉这些习惯用法，这里有一个很棒的博客系列 这里 解释了涉及的各种概念。

许可证：MIT OR Apache-2.0