Trait recursion::Expandable

source ·

pub trait Expandablewhere
    Self: Sized,{
    type FrameToken: MappableFrame;

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

Expand description

The ability to recursively expand a seed to construct a value of this type, frame by frame.

Example: A tree of integers

Here’s an example showing how to use Expandable to expand a binary tree of integers, where nodes hold two subnodes and no data and leaves hold a single usize value

#[derive(Debug, PartialEq, Eq)]
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 Expandable

Then we can define an Expandable instance for IntTree

impl Expandable for IntTree {
    type FrameToken = IntTreeFrame<PartiallyApplied>;

    fn from_frame(val: <Self::FrameToken as MappableFrame>::Frame<Self>) -> Self {
        match val {
            IntTreeFrame::Leaf { value } => IntTree::Leaf { value },
            IntTreeFrame::Node { left, right } => IntTree::Node {
                left: Box::new(left),
                right: Box::new(right),
            },
        }
    }
}

Expanding a value into a tree

Finally, we can use our Expandable instance to generate a tree

let depth = 2;

let expanded_tree = IntTree::expand_frames(depth, |n| {
    if n <= 0 {
        IntTreeFrame::Leaf { value: n }
    } else {
        IntTreeFrame::Node {
            left: n - 1,
            right: n - 1,
        }
    }
});

let expected = IntTree::node(
    IntTree::node(IntTree::leaf(0), IntTree::leaf(0)),
    IntTree::node(IntTree::leaf(0), IntTree::leaf(0)),
);

assert_eq!(expected, expanded_tree)

Required Associated Types§

source

type FrameToken: MappableFrame

Required Methods§

source

fn from_frame(val: <Self::FrameToken as MappableFrame>::Frame<Self>) -> Self

Given a frame holding instances of Self, generate an instance of Self

Object Safety§