recursion/recursive/
collapse.rs

1use crate::frame::{expand_and_collapse, MappableFrame};
2
3/// The ability to recursively collapse some type into some output type, frame by frame.
4///
5/// # Example: A tree of integers
6///
7/// Here's an example showing how to use [`Collapsible`] to collapse a binary tree of integers,
8/// where nodes hold two subnodes and no data and leaves hold a single `usize` value
9///
10/// ```rust
11/// # use recursion::*;
12/// enum IntTree {
13///     Leaf { value: usize },
14///     Node { left: Box<Self>, right: Box<Self> },
15/// }
16///
17/// # impl IntTree {
18/// #     fn node(left: Self, right: Self) -> Self {
19/// #         Self::Node {
20/// #             left: Box::new(left),
21/// #             right: Box::new(right),
22/// #         }
23/// #     }
24/// #     fn leaf(value: usize) -> Self {
25/// #         Self::Leaf { value }
26/// #     }
27/// # }
28/// ```
29///
30/// ## Defining a frame type
31///
32/// For working with values of type `IntTree`, we'll define an `IntTreeFrame<A>` frame type
33/// that represents a single layer of the `IntTree` structure, with `A` subbed in for `Box<Self>`
34///
35/// ```rust
36/// # use recursion::*;
37/// enum IntTreeFrame<A> {
38///     Leaf { value: usize },
39///     Node { left: A, right: A },
40/// }
41/// impl MappableFrame for IntTreeFrame<PartiallyApplied> { /*...*/
42/// #    type Frame<X> = IntTreeFrame<X>;
43/// #
44/// #    fn map_frame<A, B>(input: Self::Frame<A>, mut f: impl FnMut(A) -> B) -> Self::Frame<B> {
45/// #         match input {
46/// #             IntTreeFrame::Leaf { value } => IntTreeFrame::Leaf { value },
47/// #             IntTreeFrame::Node { left, right } => IntTreeFrame::Node {
48/// #                 left: f(left),
49/// #                 right: f(right),
50/// #             },
51/// #         }
52/// #     }
53/// }
54/// ```
55///
56/// ## Implementing Collapsible
57///
58/// Then we can define a collapse instance for `IntTree`
59///
60/// ```rust
61/// # use recursion::*;
62/// # enum IntTree {
63/// #     Leaf { value: usize },
64/// #     Node { left: Box<Self>, right: Box<Self> },
65/// # }
66/// # impl IntTree {
67/// #   fn node(left: Self, right: Self) -> Self { Self::Node{left: Box::new(left), right: Box::new(right)}}
68/// #   fn leaf(value: usize) -> Self { Self::Leaf{value}}
69/// # }
70/// # enum IntTreeFrame<A> {
71/// #     Leaf { value: usize },
72/// #     Node { left: A, right: A },
73/// # }
74/// # impl MappableFrame for IntTreeFrame<PartiallyApplied> {
75/// #    type Frame<X> = IntTreeFrame<X>;
76/// #
77/// #    fn map_frame<A, B>(input: Self::Frame<A>, mut f: impl FnMut(A) -> B) -> Self::Frame<B> {
78/// #         match input {
79/// #             IntTreeFrame::Leaf { value } => IntTreeFrame::Leaf { value },
80/// #             IntTreeFrame::Node { left, right } => IntTreeFrame::Node {
81/// #                 left: f(left),
82/// #                 right: f(right),
83/// #             },
84/// #         }
85/// #     }
86/// # }
87/// impl<'a> Collapsible for &'a IntTree {
88///     type FrameToken = IntTreeFrame<PartiallyApplied>;
89///
90///     fn into_frame(self) -> <Self::FrameToken as MappableFrame>::Frame<Self> {
91///         match self {
92///             IntTree::Leaf { value } => IntTreeFrame::Leaf { value: *value },
93///             IntTree::Node { left, right } => IntTreeFrame::Node {
94///                 left: left.as_ref(),
95///                 right: right.as_ref(),
96///             },
97///         }
98///     }
99/// }
100/// ```
101///
102/// ## Collapsing a tree into a value
103///
104/// Finally, we can use our [`Collapsible`] instance to collapse an example tree into a single value.
105/// In this case, we're just doing something simple - counting the number of leaves in the structure
106///
107/// ```rust
108/// # use recursion::*;
109/// # #[derive(Debug, PartialEq, Eq)]
110/// # enum IntTree {
111/// #     Leaf { value: usize },
112/// #     Node { left: Box<Self>, right: Box<Self> },
113/// # }
114/// # impl IntTree {
115/// #   fn node(left: Self, right: Self) -> Self { Self::Node{left: Box::new(left), right: Box::new(right)}}
116/// #   fn leaf(value: usize) -> Self { Self::Leaf{value}}
117/// # }
118///
119/// # enum IntTreeFrame<A> {
120/// #     Leaf { value: usize },
121/// #     Node { left: A, right: A },
122/// # }
123/// # impl MappableFrame for IntTreeFrame<PartiallyApplied> {
124/// #    type Frame<X> = IntTreeFrame<X>;
125/// #
126/// #    fn map_frame<A, B>(input: Self::Frame<A>, mut f: impl FnMut(A) -> B) -> Self::Frame<B> {
127/// #         match input {
128/// #             IntTreeFrame::Leaf { value } => IntTreeFrame::Leaf { value },
129/// #             IntTreeFrame::Node { left, right } => IntTreeFrame::Node {
130/// #                 left: f(left),
131/// #                 right: f(right),
132/// #             },
133/// #         }
134/// #     }
135/// # }
136/// # impl<'a> Collapsible for &'a IntTree {
137/// #     type FrameToken = IntTreeFrame<PartiallyApplied>;
138/// #
139/// #     fn into_frame(self) -> <Self::FrameToken as MappableFrame>::Frame<Self> {
140/// #         match self {
141/// #             IntTree::Leaf { value } => IntTreeFrame::Leaf { value: *value },
142/// #             IntTree::Node { left, right } => IntTreeFrame::Node {
143/// #                 left: left.as_ref(),
144/// #                 right: right.as_ref(),
145/// #             },
146/// #         }
147/// #     }
148/// # }
149/// let tree = IntTree::node(
150///     IntTree::node(IntTree::leaf(0), IntTree::leaf(0)),
151///     IntTree::node(IntTree::leaf(0), IntTree::leaf(0)),
152/// );
153///
154/// let leaf_count = tree.collapse_frames(|frame| match frame {
155///     IntTreeFrame::Leaf { value } => 1,
156///     IntTreeFrame::Node { left, right } => left + right,
157/// });
158///
159/// assert_eq!(leaf_count, 4)
160/// ```
161
162pub trait Collapsible
163where
164    Self: Sized,
165{
166    type FrameToken: MappableFrame;
167
168    /// Given an instance of this type, generate a frame holding the data owned by it,
169    /// with any recursive instances of `Self` owned by this node as the frame elements
170    fn into_frame(self) -> <Self::FrameToken as MappableFrame>::Frame<Self>;
171}
172
173pub trait CollapsibleExt: Collapsible
174where
175    Self: Sized,
176{
177    /// Given an instance of this type, collapse it into a single value of type `Out` by
178    /// traversing the recursive structure of `self`, generating frames, and collapsing
179    /// those frames using some function from `Frame<Out> -> Out`
180    fn collapse_frames<Out>(
181        self,
182        collapse_frame: impl FnMut(<Self::FrameToken as MappableFrame>::Frame<Out>) -> Out,
183    ) -> Out;
184
185    /// Given an instance of this type, collapse it into a single value of type `Result<Out, E>` by
186    /// traversing the recursive structure of `self`, generating frames, and collapsing
187    /// those frames using some function from `Frame<Out> -> Result<Out, E>`
188    fn try_collapse_frames<Out, E>(
189        self,
190        collapse_frame: impl FnMut(<Self::FrameToken as MappableFrame>::Frame<Out>) -> Result<Out, E>,
191    ) -> Result<Out, E>;
192}
193
194impl<X> CollapsibleExt for X
195where
196    X: Collapsible,
197{
198    fn collapse_frames<Out>(
199        self,
200        collapse_frame: impl FnMut(<Self::FrameToken as MappableFrame>::Frame<Out>) -> Out,
201    ) -> Out {
202        expand_and_collapse::<Self::FrameToken, Self, Out>(self, Self::into_frame, collapse_frame)
203    }
204
205    // TODO: add example here in this file
206    fn try_collapse_frames<Out, E>(
207        self,
208        collapse_frame: impl FnMut(<Self::FrameToken as MappableFrame>::Frame<Out>) -> Result<Out, E>,
209    ) -> Result<Out, E> {
210        crate::frame::try_expand_and_collapse::<Self::FrameToken, Self, Out, E>(
211            self,
212            |seed| Ok(Self::into_frame(seed)),
213            collapse_frame,
214        )
215    }
216}
recursion/recursive/collapse.rs

recursion/recursive/
collapse.rs
