recursion/
lib.rs

1/*!
2
3Tools for working with recursive data structures in a concise, stack safe, and performant manner.
4
5
6This crate provides abstractions for separating the _machinery_ of recursion from the _logic_ of recursion.
7This is similar to how iterators separate the _machinery_ of iteration from the _logic_ of iteration, allowing us to go from this:
8
9```rust
10# let prices = vec![1, 2, 3];
11let mut n = 0;
12while n < prices.len() {
13    print!("{}", prices[n]);
14    n += 1;
15}
16```
17
18to this:
19
20```rust
21# let prices = vec![1, 2, 3];
22for n in prices.iter() {
23    print!("{}", n)
24}
25```
26
27This second example is less verbose, has less boilerplate, and is generally nicer to work with. This crate
28aims to provide similar tools for working with recursive data structures.
29
30# Here's how it works: Expr
31
32For these examples, we will be using a simple recursive data structure - an expression language
33that supports a few mathematical operations.
34
35```rust
36pub enum Expr {
37    Add(Box<Expr>, Box<Expr>),
38    Sub(Box<Expr>, Box<Expr>),
39    Mul(Box<Expr>, Box<Expr>),
40    LiteralInt(i64),
41}
42```
43
44For working with this `Expr` type we'll define a _frame_ type `ExprFrame<A>`.
45It's exactly the same as `Expr`, except the recursive self-reference `Box<Self>` is replaced with `A`.
46This may be a bit confusing at first, but this idiom unlocks a lot of potential (expressiveness, stack safety, etc).
47You can think of `ExprFrame<A>` as representing a single _stack frame_ in a recursive algorithm.
48
49```rust
50pub enum ExprFrame<A> {
51    Add(A, A),
52    Sub(A, A),
53    Mul(A, A),
54    LiteralInt(i64),
55}
56```
57
58Now all we need is some mechanical boilerplate: [`MappableFrame`] for `ExprFrame` and [`Expandable`] and [`Collapsible`] for `Expr`.
59I'll elide that for now, but you can read the documentation for the above traits to learn what they do and how to implement them.
60
61# Collapsing an Expr into a value
62
63Here's how to evaluate an `Expr` using this idiom, by collapsing it frame by frame via a function `ExprFrame<i64> -> i64`:
64
65```rust
66# pub enum Expr {
67#     Add(Box<Expr>, Box<Expr>),
68#     Sub(Box<Expr>, Box<Expr>),
69#     Mul(Box<Expr>, Box<Expr>),
70#     LiteralInt(i64),
71# }
72#     fn add(a: Expr, b: Expr) -> Expr {
73#         Expr::Add(Box::new(a), Box::new(b))
74#     }
75#     fn subtract(a: Expr, b: Expr) -> Expr {
76#         Expr::Sub(Box::new(a), Box::new(b))
77#     }
78#     fn multiply(a: Expr, b: Expr) -> Expr {
79#         Expr::Mul(Box::new(a), Box::new(b))
80#     }
81#     fn literal(n: i64) -> Expr {
82#         Expr::LiteralInt(n)
83#     }
84# pub enum ExprFrame<A> {
85#     Add(A, A),
86#     Sub(A, A),
87#     Mul(A, A),
88#     LiteralInt(i64),
89# }
90# use recursion::*;
91# impl MappableFrame for ExprFrame<PartiallyApplied> {
92#     type Frame<X> = ExprFrame<X>;
93#     fn map_frame<A, B>(input: Self::Frame<A>, mut f: impl FnMut(A) -> B) -> Self::Frame<B> {
94#         match input {
95#             ExprFrame::Add(a, b) => ExprFrame::Add(f(a), f(b)),
96#             ExprFrame::Sub(a, b) => ExprFrame::Sub(f(a), f(b)),
97#             ExprFrame::Mul(a, b) => ExprFrame::Mul(f(a), f(b)),
98#             ExprFrame::LiteralInt(x) => ExprFrame::LiteralInt(x),
99#         }
100#     }
101# }
102# impl<'a> Collapsible for &'a Expr {
103#     type FrameToken = ExprFrame<PartiallyApplied>;
104#     fn into_frame(self) -> <Self::FrameToken as MappableFrame>::Frame<Self> {
105#         match self {
106#             Expr::Add(a, b) => ExprFrame::Add(a, b),
107#             Expr::Sub(a, b) => ExprFrame::Sub(a, b),
108#             Expr::Mul(a, b) => ExprFrame::Mul(a, b),
109#             Expr::LiteralInt(x) => ExprFrame::LiteralInt(*x),
110#         }
111#     }
112# }
113fn eval(e: &Expr) -> i64 {
114    e.collapse_frames(|frame| match frame {
115        ExprFrame::Add(a, b) => a + b,
116        ExprFrame::Sub(a, b) => a - b,
117        ExprFrame::Mul(a, b) => a * b,
118        ExprFrame::LiteralInt(x) => x,
119    })
120}
121
122let expr = multiply(subtract(literal(1), literal(2)), literal(3));
123assert_eq!(eval(&expr), -3);
124```
125
126Here's a GIF visualizing the operation of `collapse_frames`:
127
128<img src="https://raw.githubusercontent.com/inanna-malick/recursion/84806b5ce8a9e12ef7d1664d031e215922bfbaa6/recursion/img_assets/eval.gif" width="600">
129
130# Fallible functions
131
132At this point, you may have noticed that we've ommited division, which is a fallible operation
133because division by 0 is undefined. Many real world algorithms also have to handle failible operations,
134such as this. That's why this crate also provides tools for collapsing and expanding recursive data
135structures using fallible functions, like (in this case) `ExprFrame<i64> -> Result<i64, Err>`.
136
137
138```rust
139# pub enum Expr {
140#     Add(Box<Expr>, Box<Expr>),
141#     Sub(Box<Expr>, Box<Expr>),
142#     Mul(Box<Expr>, Box<Expr>),
143#     Div(Box<Expr>, Box<Expr>),
144#     LiteralInt(i64),
145# }
146#     fn add(a: Expr, b: Expr) -> Expr {
147#         Expr::Add(Box::new(a), Box::new(b))
148#     }
149#     fn subtract(a: Expr, b: Expr) -> Expr {
150#         Expr::Sub(Box::new(a), Box::new(b))
151#     }
152#     fn multiply(a: Expr, b: Expr) -> Expr {
153#         Expr::Mul(Box::new(a), Box::new(b))
154#     }
155#     fn divide(a: Expr, b: Expr) -> Expr {
156#         Expr::Div(Box::new(a), Box::new(b))
157#     }
158#     fn literal(n: i64) -> Expr {
159#         Expr::LiteralInt(n)
160#     }
161# pub enum ExprFrame<A> {
162#     Add(A, A),
163#     Sub(A, A),
164#     Mul(A, A),
165#     Div(A, A),
166#     LiteralInt(i64),
167# }
168# use recursion::*;
169# impl MappableFrame for ExprFrame<PartiallyApplied> {
170#     type Frame<X> = ExprFrame<X>;
171#     fn map_frame<A, B>(input: Self::Frame<A>, mut f: impl FnMut(A) -> B) -> Self::Frame<B> {
172#         match input {
173#             ExprFrame::Add(a, b) => ExprFrame::Add(f(a), f(b)),
174#             ExprFrame::Sub(a, b) => ExprFrame::Sub(f(a), f(b)),
175#             ExprFrame::Mul(a, b) => ExprFrame::Mul(f(a), f(b)),
176#             ExprFrame::Div(a, b) => ExprFrame::Div(f(a), f(b)),
177#             ExprFrame::LiteralInt(x) => ExprFrame::LiteralInt(x),
178#         }
179#     }
180# }
181# impl<'a> Collapsible for &'a Expr {
182#     type FrameToken = ExprFrame<PartiallyApplied>;
183#     fn into_frame(self) -> <Self::FrameToken as MappableFrame>::Frame<Self> {
184#         match self {
185#             Expr::Add(a, b) => ExprFrame::Add(a, b),
186#             Expr::Sub(a, b) => ExprFrame::Sub(a, b),
187#             Expr::Mul(a, b) => ExprFrame::Mul(a, b),
188#             Expr::Div(a, b) => ExprFrame::Div(a, b),
189#             Expr::LiteralInt(x) => ExprFrame::LiteralInt(*x),
190#         }
191#     }
192# }
193
194fn try_eval(e: &Expr) -> Result<i64, &str> {
195    e.try_collapse_frames(|frame| match frame {
196                ExprFrame::Add(a, b) => Ok(a + b),
197                ExprFrame::Sub(a, b) => Ok(a - b),
198                ExprFrame::Mul(a, b) => Ok(a * b),
199                ExprFrame::Div(a, b) =>
200                    if b == 0 { Err("cannot divide by zero")} else {Ok(a / b)},
201                ExprFrame::LiteralInt(x) => Ok(x),
202    })
203}
204
205let valid_expr = multiply(subtract(literal(1), literal(2)), literal(3));
206let invalid_expr = divide(literal(2), literal(0));
207
208assert_eq!(try_eval(&valid_expr), Ok(-3));
209assert_eq!(try_eval(&invalid_expr), Err("cannot divide by zero"));
210```
211
212Here's a GIF visualizing the operation of `try_collapse_frames` for `valid_expr`:
213
214<img src="https://raw.githubusercontent.com/inanna-malick/recursion/84806b5ce8a9e12ef7d1664d031e215922bfbaa6/recursion/img_assets/try_eval_valid.gif" width="600">
215
216And here's a GIF visualizing the operation of `try_collapse_frames` for `invalid_expr`:
217
218<img src="https://raw.githubusercontent.com/inanna-malick/recursion/84806b5ce8a9e12ef7d1664d031e215922bfbaa6/recursion/img_assets/try_eval_invalid.gif" width="600">
219
220# Expanding an Expr from a seed value
221
222Here's an example showing how to expand a simple `Expr` from a seed value
223
224```rust
225# #[derive(Debug, PartialEq, Eq)]
226# pub enum Expr {
227#     Add(Box<Expr>, Box<Expr>),
228#     Sub(Box<Expr>, Box<Expr>),
229#     Mul(Box<Expr>, Box<Expr>),
230#     LiteralInt(i64),
231# }
232#     fn add(a: Expr, b: Expr) -> Expr {
233#         Expr::Add(Box::new(a), Box::new(b))
234#     }
235#     fn subtract(a: Expr, b: Expr) -> Expr {
236#         Expr::Sub(Box::new(a), Box::new(b))
237#     }
238#     fn multiply(a: Expr, b: Expr) -> Expr {
239#         Expr::Mul(Box::new(a), Box::new(b))
240#     }
241#     fn literal(n: i64) -> Expr {
242#         Expr::LiteralInt(n)
243#     }
244# pub enum ExprFrame<A> {
245#     Add(A, A),
246#     Sub(A, A),
247#     Mul(A, A),
248#     LiteralInt(i64),
249# }
250# use recursion::*;
251# impl MappableFrame for ExprFrame<PartiallyApplied> {
252#     type Frame<X> = ExprFrame<X>;
253#     fn map_frame<A, B>(input: Self::Frame<A>, mut f: impl FnMut(A) -> B) -> Self::Frame<B> {
254#         match input {
255#             ExprFrame::Add(a, b) => ExprFrame::Add(f(a), f(b)),
256#             ExprFrame::Sub(a, b) => ExprFrame::Sub(f(a), f(b)),
257#             ExprFrame::Mul(a, b) => ExprFrame::Mul(f(a), f(b)),
258#             ExprFrame::LiteralInt(x) => ExprFrame::LiteralInt(x),
259#         }
260#     }
261# }
262# impl<'a> Collapsible for &'a Expr {
263#     type FrameToken = ExprFrame<PartiallyApplied>;
264#     fn into_frame(self) -> <Self::FrameToken as MappableFrame>::Frame<Self> {
265#         match self {
266#             Expr::Add(a, b) => ExprFrame::Add(a, b),
267#             Expr::Sub(a, b) => ExprFrame::Sub(a, b),
268#             Expr::Mul(a, b) => ExprFrame::Mul(a, b),
269#             Expr::LiteralInt(x) => ExprFrame::LiteralInt(*x),
270#         }
271#     }
272# }
273# impl Expandable for Expr {
274#     type FrameToken = ExprFrame<PartiallyApplied>;
275#     fn from_frame(val: <Self::FrameToken as MappableFrame>::Frame<Self>) -> Self {
276#         match val {
277#             ExprFrame::Add(a, b) => Expr::Add(Box::new(a), Box::new(b)),
278#             ExprFrame::Sub(a, b) => Expr::Sub(Box::new(a), Box::new(b)),
279#             ExprFrame::Mul(a, b) => Expr::Mul(Box::new(a), Box::new(b)),
280#             ExprFrame::LiteralInt(x) => Expr::LiteralInt(x),
281#         }
282#     }
283# }
284fn build_expr(depth: usize) -> Expr {
285    Expr::expand_frames(depth, |depth| {
286        if depth > 0 {
287            ExprFrame::Add(depth - 1, depth - 1)
288        } else {
289            ExprFrame::LiteralInt(1)
290        }
291    })
292}
293
294let expected = add(add(literal(1), literal(1)), add(literal(1), literal(1)));
295
296assert_eq!(expected, build_expr(2));
297
298```
299
300Here's a GIF visualizing the operation of `expand_frames``:
301
302<img src="https://raw.githubusercontent.com/inanna-malick/recursion/84806b5ce8a9e12ef7d1664d031e215922bfbaa6/recursion/img_assets/build_expr.gif" width="600">
303
304# Miscellaneous errata
305
306All GIFs in this documentation were generated via tooling in my `recursion-visualize` crate, via `examples/expr.rs`.
307
308If you're familiar with Haskell, you may have noticed that this crate makes heavy use of recursion schemes idioms.
309I've named the traits used with an eye towards readability for users unfamiliar with those idioms, but feel free to
310read [`MappableFrame`] as `Functor` and [`Expandable`]/[`Collapsible`] as `Corecursive`/`Recursive`. If you're not
311familiar with these idioms, there's a great blog post series [here](https://blog.sumtypeofway.com/posts/introduction-to-recursion-schemes.html) that explains the various concepts involved.
312
313*/
314mod frame;
315mod recursive;
316
317#[cfg(feature = "experimental")]
318pub mod experimental;
319
320pub use frame::{MappableFrame, PartiallyApplied, expand_and_collapse, try_expand_and_collapse};
321pub use recursive::{Collapsible, CollapsibleExt, Expandable, ExpandableExt};
recursion/lib.rs

recursion/
lib.rs
