1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

use std::{iter::once, rc::Rc};

pub struct Tree {
    node: Node,
}

pub enum Node {
    Leaf,
    Branch {
        // for cheap clones so that identical left subtrees of subsequent
        // trees can be shared
        left: Rc<Tree>,
        // could also be Rc, but is not necessary and Box should be less overhead
        right: Box<Tree>,
    },
}

impl Tree {
    pub fn apply<T>(
        &self,
        functions: &mut impl Iterator<Item = impl FnOnce(T, T) -> T>,
        values: &mut impl Iterator<Item = T>,
    ) -> Option<T> {
        match &self.node {
            Node::Leaf => values.next(),
            Node::Branch { left, right } => {
                Some(functions.next()?(left.apply(functions, values)?, right.apply(functions, values)?))
            }
        }
    }
}

pub fn catalan_trees(rank: usize) -> Box<dyn Iterator<Item = Tree>> {
    assert!(rank > 0);
    if rank == 1 {
        box once(Tree { node: Node::Leaf })
    }
    else {
        box (1..=rank - 1).flat_map(move |left_rank| {
            let right_rank = rank - left_rank;
            catalan_trees(left_rank).map(Rc::new).flat_map(move |left| {
                catalan_trees(right_rank)
                    .map(Box::new)
                    .map(move |right| Tree { node: Node::Branch { left: left.clone(), right } })
            })
        })
    }
}