Перечисление родовых структур

Question

Я хотел попытаться построить правильную реализацию чисел Пеано, используя structs, но кажется, что моя игра дженериков еще недостаточно хороша, и я мог бы использовать некоторую помощь. Я прочитал документы по дженерикам и некоторые вопросы Stackru, но они не соответствуют моему случаю.

Я ввел Peano черта и Zero а также Succ типы:

trait Peano {}

struct Zero;
struct Succ<T: Peano>(T);

И реализовал Peano черта для обоих типов, чтобы иметь возможность абстрагироваться над обоими:

impl Peano for Zero {}
impl<T> Peano for Succ<T> where T: Peano {}

Сначала я хотел реализовать std::ops::Add за Peano, но я быстро понял, что делаю что-то очень неправильное, поэтому я решил начать с чего-то более простого - перечисления:

trait Enumerate<T: Peano> {
    fn succ(&self) -> Succ<T>;
    fn pred(&self) -> Option<T>;
}

impl<T> Enumerate<T> for Zero where T: Peano {
    fn succ(&self) -> Succ<T> { Succ(*self) } // mismatched types: Zero instead of T
    fn pred(&self) -> Option<T> { None }
}

impl<T> Enumerate<T> for Succ<T> where T: Peano {
    fn succ(&self) -> Succ<T> { Succ(*self) } // mismatched types: Succ<T> instead of T
    fn pred(&self) -> Option<T> { Some(self.0) }
}

Что мне не хватает? Я экспериментировал с боксом результатов (хотя я хотел бы избежать этого, если это возможно), но ошибка просто изменилась на mismatched types: Box<Succ<T>> instead of Box<Peano>, поэтому я не уверен, что это полезно.

Полный код ниже:

trait Peano {}

#[derive(Debug, Clone, Copy, PartialEq)]
struct Zero;

#[derive(Debug, Clone, Copy, PartialEq)]
struct Succ<T: Peano>(T);

impl Peano for Zero {}
impl<T> Peano for Succ<T> where T: Peano {}

trait Enumerate<T: Peano> {
    fn succ(&self) -> Succ<T>;
    fn pred(&self) -> Option<T>;
}

impl<T> Enumerate<T> for Zero where T: Peano {
    fn succ(&self) -> Succ<T> { Succ(*self) }
    fn pred(&self) -> Option<T> { None }
}

impl<T> Enumerate<T> for Succ<T> where T: Peano {
    fn succ(&self) -> Succ<T> { Succ(*self) }
    fn pred(&self) -> Option<T> { Some(self.0) }
}

Answer 1

У тебя есть T в Enumerate... который не имеет смысла.

Если вы посмотрите на свой Peano черта, вы увидите, что он не имеет T: реализация для Succ имеет параметр, но сама черта не имеет.

То же самое относится и здесь.

Давайте начнем с ограниченной области: Enumerate это может только идти вперед.

use std::marker::Sized;

trait Peano {}

#[derive(Debug, Clone, Copy, PartialEq)]
struct Zero;

#[derive(Debug, Clone, Copy, PartialEq)]
struct Succ<T: Peano>(T);

impl Peano for Zero {}
impl<T> Peano for Succ<T> where T: Peano {}

trait Enumerate: Peano + Sized {
    fn succ(self) -> Succ<Self>;
}

impl Enumerate for Zero {
    fn succ(self) -> Succ<Self> { Succ(self) }
}

impl<T> Enumerate for Succ<T> where T: Peano {
    fn succ(self) -> Succ<Succ<T>> { Succ(self) }
}

Несколько интересных мест:

• Вы можете ссылаться на текущий тип как Self, очень полезно при определении черты, так как тип реализаторов заранее неизвестен
• Вы можете ограничить реализации черты, используя : Peano + Sized синтаксис после имени черты

---

Теперь у вас также был prev метод, который я не реализовал. Дело в том, что бессмысленно применять prev в Zero, В этом случае я предлагаю вам переименовать Enumerate в Next и я покажу, как создать Prev черта характера:

trait Prev: Peano + Sized {
    type Output: Peano + Sized;
    fn prev(self) -> Self::Output;
}

impl<T> Prev for Succ<T> where T: Peano {
    type Output = T;
    fn prev(self) -> Self::Output { self.0 }
}

Синтаксис type Output: Peano + Sized является ассоциированным типом, он позволяет каждому исполнителю указать, какой тип использовать для своего конкретного случая (и избежать того, чтобы пользователь черты мог угадать, какой тип он должен использовать).

После указания его можно назвать Self::Output внутри черты или как <X as Prev>::Output снаружи (если X инвентарь Prev).

И поскольку черта является отдельной, у вас есть только Prev реализация для Peano числа, которые на самом деле имеют предшественника.

---

Почему Sized ограничение?

На данный момент Rust требует, чтобы возвращаемые типы имели известный размер. Это предел реализации: на практике вызывающий должен зарезервировать достаточно места в стеке, чтобы вызываемый мог записать возвращаемое значение.

Однако... для вычислений на уровне типов это бесполезно! Так что же нам делать?

Ну, во-первых, мы добавим удобный метод проверки результата наших вычислений (красивее, чем Debug выход):

trait Value: Peano {
    fn value() -> usize;
}

impl Value for Zero {
    fn value() -> usize { 0 }
}

impl<T> Value for Succ<T> where T: Value {
    fn value() -> usize { T::value() + 1 }
}

fn main() {
    println!("{}", Succ::<Zero>::value());
}

Тогда... давайте избавимся от этих методов, они ничего не принесут; переработанные черты, таким образом:

trait Next: Peano {
    type Next: Peano;
}

impl Next for Zero {
    type Next = Succ<Zero>;
}

impl<T> Next for Succ<T> where T: Peano {
    type Next = Succ<Succ<T>>;
}

fn main() {
    println!("{}", <Zero as Next>::Next::value());
}

а также:

trait Prev: Peano {
    type Prev: Peano;
}

impl<T> Prev for Succ<T> where T: Peano {
    type Prev = T;
}

fn main() {
    println!("{}", <<Zero as Next>::Next as Prev>::Prev::value());
}

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