Trait recursion::Collapsible
source · pub trait Collapsiblewhere
Self: Sized,{
type FrameToken: MappableFrame;
// Required method
fn into_frame(self) -> <Self::FrameToken as MappableFrame>::Frame<Self>;
}
Expand description
The ability to recursively collapse some type into some output type, frame by frame.
Example: A tree of integers
Here’s an example showing how to use Collapsible
to collapse a binary tree of integers,
where nodes hold two subnodes and no data and leaves hold a single usize
value
enum IntTree {
Leaf { value: usize },
Node { left: Box<Self>, right: Box<Self> },
}
Defining a frame type
For working with values of type IntTree
, we’ll define an IntTreeFrame<A>
frame type
that represents a single layer of the IntTree
structure, with A
subbed in for Box<Self>
enum IntTreeFrame<A> {
Leaf { value: usize },
Node { left: A, right: A },
}
impl MappableFrame for IntTreeFrame<PartiallyApplied> { /*...*/
}
Implementing Collapsible
Then we can define a collapse instance for IntTree
impl<'a> Collapsible for &'a IntTree {
type FrameToken = IntTreeFrame<PartiallyApplied>;
fn into_frame(self) -> <Self::FrameToken as MappableFrame>::Frame<Self> {
match self {
IntTree::Leaf { value } => IntTreeFrame::Leaf { value: *value },
IntTree::Node { left, right } => IntTreeFrame::Node {
left: left.as_ref(),
right: right.as_ref(),
},
}
}
}
Collapsing a tree into a value
Finally, we can use our Collapsible
instance to collapse an example tree into a single value.
In this case, we’re just doing something simple - counting the number of leaves in the structure
let tree = IntTree::node(
IntTree::node(IntTree::leaf(0), IntTree::leaf(0)),
IntTree::node(IntTree::leaf(0), IntTree::leaf(0)),
);
let leaf_count = tree.collapse_frames(|frame| match frame {
IntTreeFrame::Leaf { value } => 1,
IntTreeFrame::Node { left, right } => left + right,
});
assert_eq!(leaf_count, 4)
Required Associated Types§
Required Methods§
sourcefn into_frame(self) -> <Self::FrameToken as MappableFrame>::Frame<Self>
fn into_frame(self) -> <Self::FrameToken as MappableFrame>::Frame<Self>
Given an instance of this type, generate a frame holding the data owned by it,
with any recursive instances of Self
owned by this node as the frame elements