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

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?

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

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

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.

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.

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

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?

`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<_>>;
}
``````