Shared via Rust Playground

playground.rs

use std::marker::PhantomData;

trait Num {
    fn eval() -> i32;
}

struct Zero<T: Num>(PhantomData<T>);
struct One<T: Num>(PhantomData<T>);
struct Nothing;

trait Something: Num {}
impl<T: Num> Something for Zero<T> {}
impl<T: Num> Something for One<T> {}

type NumZero = Zero<Nothing>;
type NumOne = One<Nothing>;

impl<T: Num> Num for Zero<T> {
    fn eval() -> i32 { T::eval() * 2 }
}

impl<T: Num> Num for One<T> {
    fn eval() -> i32 { T::eval() * 2 + 1 }
}
impl Num for Nothing {
    fn eval() -> i32 { 0 }
}

trait Add<Y: Num>: Num {
    type Out: Num;
}

impl<X, Y> Add<Y> for X
where Y: Num,
      X: AddCarry<Y, NumZero> {
    type Out = X::Out;
}

trait AddCarry<Y: Num, C: Num>: Num {
    type Out: Num;
}

impl<X, Y> AddCarry<Zero<Y>, NumZero> for Zero<X>
where Y: Num,
      X: AddCarry<Y, NumZero> {
    type Out = Zero<X::Out>;
}

impl<X, Y> AddCarry<One<Y>, NumZero> for Zero<X>
where Y: Num,
      X: AddCarry<Y, NumZero> {
    type Out = One<X::Out>; 
}

impl<X, Y> AddCarry<Zero<Y>, NumOne> for Zero<X>
where Y: Num,
      X: AddCarry<Y, NumZero> {
    type Out = One<X::Out>;
}

impl<X, Y> AddCarry<One<Y>, NumOne> for Zero<X>
where Y: Num,
      X: AddCarry<Y, NumOne> {
    type Out = Zero<X::Out>;
}

impl<X, Y> AddCarry<Zero<Y>, NumZero> for One<X>
where Y: Num,
      X: AddCarry<Y, NumZero> {
    type Out = One<X::Out>;
}

impl<X, Y> AddCarry<One<Y>, NumZero> for One<X>
where Y: Num,
      X: AddCarry<Y, NumOne> {
    type Out = Zero<X::Out>; 
}

impl<X, Y> AddCarry<Zero<Y>, NumOne> for One<X>
where Y: Num,
      X: AddCarry<Y, NumOne> {
    type Out = Zero<X::Out>;
}

impl<X, Y> AddCarry<One<Y>, NumOne> for One<X>
where Y: Num,
      X: AddCarry<Y, NumOne> {
    type Out = One<X::Out>;
}

impl<X: Num> AddCarry<Nothing, NumZero> for X {
    type Out = X;
}

impl<X> AddCarry<Nothing, NumOne> for X 
where X: AddCarry<NumOne, NumZero> {
    type Out = X::Out;
}

impl<Y: Something> AddCarry<Y, NumZero> for Nothing {
    type Out = Y;
}

impl<Y> AddCarry<Y, NumOne> for Nothing
where Y: AddCarry<NumOne, NumZero> + Something {
    type Out = Y::Out;
}

fn main() {
    println!("{}", <One<Zero<NumOne>> as Add<One<One<NumOne>>>>::Out::eval());
}