Есть ли способ имитировать универсальные связанные типы / конструкторы связанных типов в Rust? - PullRequest
Новая
       41

Есть ли способ имитировать универсальные связанные типы / конструкторы связанных типов в Rust?

0 голосов
/ 12 января 2019

Я делаю модуль обработки графиков в Rust. Ядро модуля моделирует идею наличия нескольких контейнеров, которые содержат данные на графике. Например, у меня может быть график, внутренняя структура которого равна HashMap или, возможно, AdjacencyMatrix и т. Д.

Эти контейнеры должны реализовывать черту: 

trait GraphData<V> {
    fn has_edge(&self, v: &V, u: &V) -> bool;
    fn nodes(&self) -> Iterator<V>; // Here's the problem...
}

Я не могу просто вернуть черту в своем определении черты. Я знаю, что должен использовать объект черты, но я не хочу Box его. Я хотел бы, чтобы контейнер предоставил свою собственную NodeIter структуру. Однако я застрял бы с той же проблемой, объясненной в Конструкторы связанного типа, часть 1: основные понятия и введение . В этом посте рассказывается о конструкторах связанных типов (ATC), которых нет в Rust. Мой GraphData напоминает описанный Collection.

Есть ли какой-нибудь обходной путь, который я мог бы использовать для "имитации" УВД, или какой-либо другой шаблон, специфичный для Rust, который я мог бы использовать для этой ситуации?

Я не хочу зависеть от динамической отправки и прибегать к использованию Box или ключевому слову dyn.

Я думал определить структуру NodeIter для каждого типа контейнера графа. Я создал в своем модуле и добавил «узлы» внутри реализации самого контейнера. Однако я считаю, что это плохое повторное использование кода.

Ответы [ 2 ]

0 голосов
/ 06 февраля 2019

Как и в ответе Андерса Касерога , уже объясняется: вам, возможно, здесь не нужны GAT, если вы можете жить с клонированием вашего Vec, содержащего вершины. Однако, это, вероятно, не то, что вы хотите. Вместо этого вы обычно хотите иметь итератор, который ссылается на исходные данные.

Чтобы достичь этого, вы на самом деле в идеале хотите использовать GAT. Но поскольку они еще не являются частью языка, давайте ответим на ваш главный вопрос: Есть ли способ имитировать родовые связанные типы? На самом деле я написал очень обширное сообщение в блоге на эту тему: «Решение обобщенной задачи потокового итератора без GAT» .

Подводя итог статьи:

  • Самый простой способ для вас - поместить итератор в коробку и вернуть его в качестве объекта черты: 

    fn nodes(&self) -> Box<dyn Iterator<&'_ V> + '_>

    Как вы сказали, вы этого не хотите, так что этого нет.

  • Вы можете добавить параметр времени жизни к своей характеристике и использовать это время жизни в вашем связанном типе и &self получателе: 

    trait GraphData<'s, V: 's> {
    type NodesIter: Iterator<Item = &'s V>;
    fn nodes(&'s self) -> Self::NodesIter;
}

struct MyGraph<V> {
    nodes: Vec<V>,
}

impl<'s, V: 's> GraphData<'s, V> for MyGraph<V> {
    type NodesIter = std::slice::Iter<'s, V>;
    fn nodes(&'s self) -> Self::NodesIter {
        self.nodes.iter()
    }
}

    Это работает! Однако теперь у вас есть раздражающий параметр времени жизни в вашей черте. Это может быть хорошо (кроме раздражения) в вашем случае, но на самом деле это может быть критической проблемой в некоторых ситуациях, так что это может или не может работать для вас.

  • Вы можете продвинуть параметр времени жизни на уровень глубже, имея вспомогательную черту, которая работает как функция уровня типа от времени жизни к типу. Это делает ситуацию немного менее раздражающей, поскольку параметр времени жизни больше не является вашей основной чертой, но он страдает тем же ограничением, что и предыдущий обходной путь.

  • Вы также можете пойти совершенно другим путем и написать обертку итератора, которая содержит ссылку на ваш график.

    Это всего лишь грубый набросок, но основная идея работает: ваш реальный внутренний итератор не содержит ссылок на график (поэтому для его типа не требуется время жизни self). Ссылка на график вместо этого сохраняется в определенном типе Wrap и передается внутреннему итератору для каждого вызова next.

    Как это: 

    trait InnerNodesIter { /* ... */ }

struct Wrap<'graph, G: GraphData, I: InnerNodesIter> {
    graph: &'graph G,
    iter: I,
}

type NodesIterInner: InnerNodesIter;
fn nodes(&self) -> Wrap<'_, Self, Self::NodesIterInner>;

    Тогда вы можете реализовать Iterator для Wrap. Вам просто нужен некоторый интерфейс для внутреннего итератора, который вы можете передать ссылку на график. Что-то вроде fn next(&mut self, graph: &Graph) -> Option<...>. Вам нужно определить интерфейс в InnerNodesIter.

    Это, конечно, очень многословно. И это также может быть немного медленнее, в зависимости от того, как работает ваш итератор.

Краткое и грустное резюме таково: Не существует удовлетворительного обходного пути, подходящего для любой ситуации.

Мое мнение в этом случае: я работаю над проектом, в котором эта точная ситуация возникала несколько раз. В моем случае я просто использовал решение Box, поскольку оно очень простое и отлично работает. Единственным недостатком является скорость (распределение и динамическая диспетчеризация), но распределение не происходит в узком цикле (кроме случаев, когда у вас большое количество графиков, в каждом из которых очень мало узлов - маловероятно), и оптимизатор, вероятно, способен девиртуализации динамических вызовов в большинстве случаев (в конце концов, информация о реальном типе находится всего в одной функции).

0 голосов
/ 13 января 2019

Проблема, которую вы описали, решается с помощью простых связанных типов . Он не требует универсальных связанных типов , a.k.a. конструкторов связанных типов. Это уже работает в стабильном Rust. 

trait GraphData<V> {
    type Nodes: Iterator<Item = V>;
    fn has_edge(&self, v: &V, u: &V) -> bool;
    fn nodes(&self) -> Self::Nodes;
}

struct Graph<V> {
    nodes: Vec<V>,
    edges: Vec<(V, V)>,
}

impl<V: Clone + Eq> GraphData<V> for Graph<V> {
    type Nodes = vec::IntoIter<V>;
    fn has_edge(&self, u: &V, v: &V) -> bool {
        self.edges.iter().any(|(u1, v1)| u == u1 && v == v1)
    }
    fn nodes(&self) -> Self::Nodes {
        self.nodes.clone().into_iter()
    }
}

Nodes не имеет параметров типа или времени жизни (это не Nodes<T> или Nodes<'a>), поэтому он не является общим.

Если вы хотите, чтобы тип Nodes мог содержать ссылку на Self (чтобы избежать clone()), , тогда Nodes должен быть универсальным с параметром времени жизни. Но это не единственный способ избежать clone(): вы можете использовать Rc.

...