How to express that two traits must each have a method that returns an instance of the other


#1

I am a scientific programmer learning Rust. I am trying to implement a simple linear algebra interface, mainly to learn the language. Ultimately, I would like an interface that would allow writing function signatures like this, which would make writing most linear algebra algorithms quite simple:

do_math<Element>(&RowVector<Element>, &ColumnVector<Element>)

I would like RowVector and ColumnVector to be traits so that there can different implementations (e.g. dense vs sparse). However, I am struggling to implement the basic operation: transpose. Namely, I don’t know how to say in Rust, “The transpose of a RowVector is a ColumnVector and vice versa.” I was lead on StackOverflow to something closer than I had before. But ultimately could not put together a complete solution, because it involves a cyclic type definition:

#[macro_use]
extern crate derive_new;

trait Transpose<To> {
    fn transpose(self) -> To;
}

trait RowVector<Element> : Transpose<ColumnVector<Element>> {
}

trait ColumnVector<Element> : Transpose<RowVector<Element>> {
}

#[derive(new, Debug)]
struct VecRowVector<Element> {
    vec: Vec<Element>
}

#[derive(new, Debug)]
struct VecColumnVector<Element> {
    vec: Vec<Element>
}

impl<Element> Transpose<VecColumnVector<Element>> for VecRowVector<Element> {
    fn transpose(self) -> VecColumnVector<Element> {
        VecColumnVector::new(self.vec)
    }
}

impl<Element> Transpose<VecRowVector<Element>> for VecColumnVector<Element> {
    fn transpose(self) -> VecRowVector<Element> {
        VecRowVector::new(self.vec)
    }
}

fn main() {
    let row_vector = VecRowVector::new(vec![1,2,3]);
    let col_vector = VecColumnVector::new(vec![1,2,3]);
    println!("{:?}", row_vector.transpose());
    println!("{:?}", col_vector.transpose());
}

What is the standard Rust way to express relationships like this, that each trait has a method that returns an instance of the other?


#2

If you’re willing to drop support for trait objects and use generics, you can use an associated type as follows.

trait Transpose: Sized {
    type Transpose: Transpose<Transpose = Self>;

    fn transpose(self) -> Self::Transpose;
}

trait RowVector<Element>: Transpose
    where Self::Transpose: ColumnVector<Element>
{}
trait ColumnVector<Element>: Transpose
    where Self::Transpose: RowVector<Element>
{}

#[derive(Debug)]
struct VecRowVector<Element> {
    vec: Vec<Element>
}

impl<Element> VecRowVector<Element> {
    pub fn new(vec: Vec<Element>) -> Self {
        VecRowVector { vec: vec }
    }
}


impl<Element> RowVector<Element> for VecRowVector<Element> {}
impl<Element> ColumnVector<Element> for VecColumnVector<Element> {}

#[derive(Debug)]
struct VecColumnVector<Element> {
    vec: Vec<Element>
}

impl<Element> VecColumnVector<Element> {
    pub fn new(vec: Vec<Element>) -> Self {
        VecColumnVector { vec: vec }
    }
}

impl<Element> Transpose for VecRowVector<Element> {
    type Transpose = VecColumnVector<Element>;
    fn transpose(self) -> Self::Transpose {
        VecColumnVector::new(self.vec)
    }
}

impl<Element> Transpose for VecColumnVector<Element> {
    type Transpose = VecRowVector<Element>;
    fn transpose(self) -> Self::Transpose {
        VecRowVector::new(self.vec)
    }
}

fn main() {
    let row_vector = VecRowVector::new(vec![1,2,3]);
    let col_vector = VecColumnVector::new(vec![1,2,3]);
    println!("{:?}", row_vector.transpose());
    println!("{:?}", col_vector.transpose());
}

#3

If I lost support for trait objects, that means no dynamic dispatch, right? I couldn’t write the do_math function signature?


#4

No, but you couldn’t do that before due to your Transpose signature:

  1. To must be sized because it’s returned by-value.
  2. Self must be sized because it’s taken by-value.

Your do_math function would have to be:

fn do_math<E, R, C>(row: R, column: C)
    where R: RowVector<E, Transpose = C>,
          C: ColumnVector<E, Transpose = R>,
{}

You may be able to abstract over some kind of BoxedRowVector/BoxedColumnVector etc.


#5

If you don’t need to transpose between R and C you can do the following:

fn do_math<E, R1, C1, R2, C2>(row: R1, column: C2)
    where R2: RowVector<E, Transpose = C2>,
          C2: ColumnVector<E, Transpose = R2>,
          R1: RowVector<E, Transpose = C1>,
          C1: ColumnVector<E, Transpose = R1>,
{}

It would be nice to one omit some of those constraints (we don’t care about R2 and C1) but I don’t think it’s possible.


#6

Ah, I was wrong. You can write:

fn do_math<E, R, C>(row: R, column: C)
    where R: RowVector<E>,
          R::Transpose: ColumnVector<E>, // Should be implied
          C: ColumnVector<E>,
          C::Transpose: RowVector<E>, // Should be implied.
{}

(but rust really should infer that).


#7

I think I have gotten closer by having transpose return a Box and dropping the Transpose trait entirely. At least the traits and impls all compile, I just need to figure out how actually use the types.

use std::fmt::Debug;

trait RowVector<Element: 'static + Debug>: Debug {
    fn transpose(self) -> Box<ColumnVector<Element>>;
}

trait ColumnVector<Element: 'static + Debug>: Debug {
    fn transpose(self) -> Box<RowVector<Element>>;
}

#[derive(Debug)]
struct VecRowVector<Element: 'static> {
    vec: Vec<Element>
}

#[derive(Debug)]
struct VecColumnVector<Element: 'static> {
    vec: Vec<Element>
}

impl<Element: Debug> RowVector<Element> for VecRowVector<Element> {
    fn transpose(self) -> Box<ColumnVector<Element>> {
        Box::new(VecColumnVector { vec: self.vec })
    }
}

impl<Element: Debug> ColumnVector<Element> for VecColumnVector<Element> {
    fn transpose(self) -> Box<RowVector<Element>> {
        Box::new(VecRowVector { vec: self.vec })
    }
}

fn main() {
    // &RowVector is probably not the right type; I need ownership of the data
    fn do_math<Element: 'static + Debug>(row: &RowVector<Element>) -> Box<ColumnVector<Element>> {
        row.transpose()
    }

    // This type works perfectly for my readonly methods (e.g. `length` not shown). 
    // What do I use when I need ownership?
    let row_vector: &RowVector<i64> = &VecRowVector { vec: vec![1, 2, 3] };
    let column_vector = do_math(row_vector);
}

These are the errors:

error[E0161]: cannot move a value of type RowVector<Element>: the size of RowVector<Element> cannot be statically determined
  --> src\main.rs:78:5
   |
78 |     row.transpose()
   |     ^^^

error[E0507]: cannot move out of borrowed content
  --> src\main.rs:78:5
   |
78 |     row.transpose()
   |     ^^^ cannot move out of borrowed content

I think I understand why I get the error: the trait object is a borrowed pointer when I need an owned pointer. What is the owned pointer equivalent of a trait object? Is there any pointer with move sematics and dynamic dispatch?


#8

Box<Trait>

Unfortunately, this is a big pain point for rust right now. If you’re interested, take a look at how the standard library deals with Box<FnOnce>.

I’ve used the same solution in the following vector implementation:

trait Transpose: Sized {
    type Transpose: Transpose<Transpose = Self>;

    fn transpose(self) -> Self::Transpose;
}

trait RowVector<Element>: Transpose
    where Self::Transpose: ColumnVector<Element>
{}
trait ColumnVector<Element>: Transpose
    where Self::Transpose: RowVector<Element>
{}

trait RowVectorBox<E> {
    #[doc(hidden)]
    fn transpose_box(self: Box<Self>) -> Box<ColumnVectorBox<E>>;
}

impl<E, R, C> RowVectorBox<E> for R
    where R: RowVector<E, Transpose=C> + 'static,
          C: ColumnVector<E, Transpose=R> + 'static,
{
    fn transpose_box(self: Box<R>) -> Box<ColumnVectorBox<E>> {
        Box::new((*self).transpose()) as Box<ColumnVectorBox<E>>
    }
}
trait ColumnVectorBox<E> {
    #[doc(hidden)]
    fn transpose_box(self: Box<Self>) -> Box<RowVectorBox<E>>;
}

impl<E, C, R> ColumnVectorBox<E> for C
    where R: RowVector<E, Transpose=C> + 'static,
          C: ColumnVector<E, Transpose=R> + 'static,
{
    fn transpose_box(self: Box<C>) -> Box<RowVectorBox<E>> {
        Box::new((*self).transpose()) as Box<RowVectorBox<E>>
    }
}

impl<E> Transpose for Box<RowVectorBox<E>> {
    type Transpose = Box<ColumnVectorBox<E>>;
    fn transpose(self) -> Self::Transpose {
        self.transpose_box()
    }
}
impl<E> RowVector<E> for Box<RowVectorBox<E>> {}

impl<E> Transpose for Box<ColumnVectorBox<E>> {
    type Transpose = Box<RowVectorBox<E>>;
    fn transpose(self) -> Self::Transpose {
        self.transpose_box()
    }
}
impl<E> ColumnVector<E> for Box<ColumnVectorBox<E>> {}

#[derive(Debug)]
struct VecRowVector<Element> {
    vec: Vec<Element>
}

impl<Element> VecRowVector<Element> {
    pub fn new(vec: Vec<Element>) -> Self {
        VecRowVector { vec: vec }
    }
}


impl<Element> RowVector<Element> for VecRowVector<Element> {}
impl<Element> ColumnVector<Element> for VecColumnVector<Element> {}

#[derive(Debug)]
struct VecColumnVector<Element> {
    vec: Vec<Element>
}

impl<Element> VecColumnVector<Element> {
    pub fn new(vec: Vec<Element>) -> Self {
        VecColumnVector { vec: vec }
    }
}

impl<Element> Transpose for VecRowVector<Element> {
    type Transpose = VecColumnVector<Element>;
    fn transpose(self) -> Self::Transpose {
        VecColumnVector::new(self.vec)
    }
}

impl<Element> Transpose for VecColumnVector<Element> {
    type Transpose = VecRowVector<Element>;
    fn transpose(self) -> Self::Transpose {
        VecRowVector::new(self.vec)
    }
}

fn main() {
    let row_vector = VecRowVector::new(vec![1,2,3]);
    let col_vector = VecColumnVector::new(vec![1,2,3]);
    println!("{:?}", row_vector.transpose());
    println!("{:?}", col_vector.transpose());

    let boxed_row_vector = Box::new(VecRowVector::new(vec![1,2,3])) as Box<RowVectorBox<_>>;
}