Trait recursion::Collapsible

pub trait Collapsible
where
    Self: Sized,
{
    type FrameToken: MappableFrame;

    // Required method
    fn into_frame(self) -> <Self::FrameToken as MappableFrame>::Frame<Self>;
}

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

type FrameToken: MappableFrame

Required Methods

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

Object Safety

This trait is not object safe.

Implementors