Enumerating generic structs

Question

I wanted to try to build a proper implementation of Peano numbers using structs, but it seems my generics game is not good enough yet and I could use some help. I read the docs on generics and some StackOverflow questions, but they don't fit my case.

I introduced a Peano trait and Zero and Succ types:

trait Peano {}

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

And implemented a Peano trait for both types to be able to abstract over both:

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

At first I wanted to implement std::ops::Add for Peano, but I quickly saw that I was doing something very wrong, so I decided to start with something simpler - enumeration:

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) }
}

What am I missing? I experimented with boxing the results (though I would want to avoid that if possible), but the error just changed to mismatched types: Box<Succ<T>> instead of Box<Peano>, so I'm not sure this is helpful.

Full code below:

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

You have a T in Enumerate... which serves no purpose.

If you look back at your Peano trait, you will see that it has no T: the implementation for Succ has a parameter, but the trait itself does not.

The same applies here.

Let us start with a reduced scope: an Enumerate that can only go forward.

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) }
}

A few points of interest:

• you can refer to the current type as Self, very useful when defining a trait since the type of implementers is unknown in advance
• you can constrain the implementers of a trait by using the : Peano + Sized syntax after the trait name

---

Now, you also had a prev method which I did not implement. The thing is, it is nonsensical to apply prev to Zero. In this case, I propose that you rename Enumerate to Next and I'll show how to create a Prev trait:

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 }
}

The syntax type Output: Peano + Sized is an associated type, it allows each implementer to specify which type to use for their specific case (and avoid having the user of the trait, having to guess which type they should use).

Once specified, it can be referred to as Self::Output within the trait or as <X as Prev>::Output from outside (if X implements Prev).

And since the trait is separate, you only have a Prev implementation for Peano numbers that actually have a predecessor.

---

Why the Sized constraint?

At the moment, Rust requires that return types have a known size. This is an implementation limit: in practice the caller has to reserve enough space on the stack for the callee to write down the return value.

However... for type-level computation this is useless! So, what do we do?

Well, first we add convenient method of checking the result of our computations (prettier than the Debug output):

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());
}

Then... let's get rid of those methods, they bring nothing; the reworked traits are thus:

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());
}

and:

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());
}

Now, you can go ahead and implement Add and co, though if you implement traits with methods you might need additional constraints.