Trait Collapsible

Source
pub trait Collapsible
where 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§

Source

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

Dyn Compatibility§

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors§