Я пытаюсь реализовать чисто функциональное красно-черное дерево в Rust, следуя примеру Окасаки. Когда я вставляю в красно-черное дерево, мне, возможно, придется вставить в дерево. Вот код Haskell для функции balance
:
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
В этом коде используется вложенное сопоставление. Однако в Rust это невозможно, так как для левой и правой ветвей необходимо использовать "коробочное" представление. Я использую Rc
. Вот мое определение данных для Tree<A>
:
#[derive(Clone, Debug, Eq, PartialEq)]
enum Tree<A> {
E,
T(Color, Rc<Tree<A>>, A, Rc<Tree<A>>)
}
Как я могу достичь эквивалента «вложенного соответствия», когда у меня есть Rc
s?
Я прекрасно понимаю, что это невозможно сопоставить с Rc
s. Вместо этого мне интересно, существуют ли эквивалентные идиомы программирования, которые могут достичь того же эффекта.