I'm trying to implement a purely functional red-black tree in Rust, following Okasaki's example. When I insert into a red-black tree, I might have to insert into the tree. Here's Haskell code for the balance function:
balance :: Ord a => Color -> Tree a -> a -> Tree a -> Tree a
balance Black (T Red (T Red a x b) y c) z d = T Red (T Black a x b) y (T Black c z d)
balance Black (T Red a x (T Red b y c)) z d = T Red (T Black a x b) y (T Black c z d)
balance Black a x (T Red (T Red b y c) z d) = T Red (T Black a x b) y (T Black c z d)
balance Black a x (T Red b y (T Red c z d)) = T Red (T Black a x b) y (T Black c z d)
balance c l v r = T c l v r
This code uses nested matching. However, this is not possible in Rust as one has to use a "boxed" representation for the left and right branches. I'm using an Rc. Here's my data definition for Tree<A>:
#[derive(Clone, Debug, Eq, PartialEq)]
enum Tree<A> {
E,
T(Color, Rc<Tree<A>>, A, Rc<Tree<A>>)
}
How can I achieve the equivalent of "nested matching" when I have Rcs?
I am well aware that it is impossible to match into Rcs. Instead, I am wondering if there are equivalent programming idioms that can achieve the same effect.
