Блог*

#prog #rust #моё

Допустим, нам нужно сделать на Rust бинарное дерево. Казалось бы, плёвое дело:

struct TreeNode<T> {
    value: T,
    left: Option<Box<Self>>,
    right: Option<Box<Self>>,
}

struct Tree<T> {
    root: Option<TreeNode<T>>,
}

Однако тут у нас по аллокации на каждый узел, от чего у нас страдает локальность данных и, как следствие, эффективность кеша (не говоря уже о стоимости аллокаций в рантайме). С другой стороны, у нас есть возможность делать дерево произвольной (насколько хватит оперативки, конечно же) высоты. А можем ли мы, отказавшись от произвольной высоты и задавая её предел наперёд, хранить вложенные узлы напрямую, а не через указатель? Как оказалось, да!

Но для начала немного о том, как мы будем задавать высоту. Так как решение на const generics потребует специализации и более продвинутой их обработки и потому абсолютно не реализуемо на стабильной версии, воспользуемся для задания высоты числами Пеано (да, я об этом уже писал):

struct Z;
struct S<T>(T);

Теперь немного подумаем о том, как это отобразить на древовидную структуру. Каждый узел дерева высотой N + 1 включает в себя узлы высотой N. Узел же дерева с высотой 0 не должен включать в себя данные вообще. Этого можно добиться, сопоставив Z тип с полями ненаселённого типа.

Кажется, что это изложение довольно легко перекладывается на код: определяем трейт с ассоциированным типом, который уменьшает число на единицу, реализуем его для S<T> с типом T, а для Z с типом ~~never~~ Infallible, параметризуем узел высотой Height и параметризуем вложенные узлы <Height as Decrement>::Output... К сожалению, это не работает: если определить узел таки образом, rustc не понимает, что рекурсия рано или поздно кончается, и жалуется на бесконечную вложенность типа без индирекции. Кажется, нам нужен другой подход.

С другой стороны, так уж сильно нам его менять не придётся: вместо того, чтобы отображать каждое число на число на единицу меньше, вы воспользуемся структурной индукцией и будем отображать число непосредственно на тип узла:

struct Node<T, Next> {
    value: T,
    left: Next,
    right: Next,
}

Тут важно, что поля left и right имеют тип Next, а не Option<Next>, иначе мы не сможем сделать узел нулевой высоты ненаселённым типом. Собственно, вот как отображение выглядит для Z:

use std::convert::Infallible as Never;

trait Project<T> {
    type Projected;
}

impl<T> Project<T> for Z {
    type Projected = Node<T, Never>;
}

Итого узел нулевой высоты нельзя сконструировать, как мы и хотели. Лишь немногим сложнее выглядит отображение для S<N>:

impl<T, N> Project<T> for S<N>
where
    N: Project<T>,
{
    type Projected = Node<T, Option<N::Projected>>;
}

Так как мы не хотим оперировать узлами напрямую (хотя бы потому, что через них затруднительно наложить ограничение на высоту), сделаем обёртку — собственно параметризованное высотой дерево:

struct Tree<T, Height: Project<T>> {
    repr: Height::Projected,
}

Теперь реализуем парочку вспомогательных методов и попробуем сделать дерево высоты 2 (=S<S<Z>>):

let tree: Tree<i32, S<S<Z>>> = Node {
    value: 42,
    left: None,
    right: Some(Node {
        value: 42,
        left: None,
        right: None
    }),
}.into();

Что ж... Оно работает. И даже нормально печатается поле repr, если добавить #[derive(Debug)] на Node. Попробуем теперь поменять тип дерева на дерево с единичной высотой:

let tree: Tree<i32, S<Z>> = Node {
   ...

Компилятор ожидаемо жалуется:

error[E0271]: type mismatch resolving <Z as Project<i32>>::Projected == Node<{integer}, Option<_>>
   --> src/main.rs:181:7
    |
181 |     }.into();
    |       ^^^^ expected enum Option, found enum Infallible
    |
    = note: expected struct Node<{integer}, Option<_>>
               found struct Node<i32, Infallible>

Не слишком внятно, но цели статически ограничить высоту дерева мы успешно достигли.

Как всегда, весь код в гисте. И на этот раз даже больше, чем в посте: добавлены методы для поиска по дереву (с допущением, что дерево является двоичным деревом поиска) и немного более приятная печать.

Оставайтесь на связи. 🤙