Add trait is not enough

[bluss]

Add does not propagate useful information for generic code:

We need to know that if we add two Unsigned, the Output is also Unsigned, so that we can continue performing interesting arithmetic on it, or use it as a typenum input to for example generic-array.

[paholg]

Could you give me an example of where the current method doesn't work, or of what a better Add trait would look like? It's sometimes ugly, but I've always gotten typenum to do what I need it to do the way it is. I played around with custom operator traits at the beginning, but never found anything that works better than the ones in std::ops.

For example, a function to concatenate two generic arrays might look something like this:

fn concat<T, M, N>(a: GenericArray<T, M>, b: GenericArray<T, N>) -> GenericArray<T, Sum<M, N>>
    where M: ArrayLength<T> + Add<N>, N: ArrayLength<T>, Sum<M, N>: ArrayLength<T>
{
    // ...
}

[bluss]

I was trying to convert this to generic array:

struct Entry<K, V> {
    keys: ArrayVec<[K; MAX_ORDER - 1]>,
    values: ArrayVec<[V; MAX_ORDER - 1]>,
    children: ArrayVec<[Box<Entry<K, V>>; MAX_ORDER]>,
    parent: *mut Entry<K, V>,
    position: usize,
}

Instead of the constant max order, you'd use one type parameter for "B" or so, and have one array be 2B + 1 and another 2B + 2.

The entry is part of a public api (a map), that would have the same Unsigned type parameter. I just found that there is no neat way to do this, it would have a huge set of where bounds unfortunately.

pub struct Bmap<K, V> {
    length: usize,
    root: Box<Entry<K, V>>,
}

[paholg]

I think, unfortunately, lots of where bounds are necessary for working with typenum. I wish there were a way to say something like "where the minimum necessary constraints are satisfied". The compiler clearly has this information, as it can tell you exactly what where bounds you need to add.

Anyway, I would be happy to implement an alternative Add trait (and for other operators too), but I don't know how that could help with this problem. Any ideas you have for how that would work are welcome, but I've tried a decent amount to increase the ergonomics of typenum and its present state is the best I've been able to do.

[bluss]

It's a very cool library, but it's not suited for what I was trying to do: A B-tree with B as a type parameter.

Even writing in primitives like Uint<B, B0> and Uint<B, B1> (2B and 2B + 1 respectively), there were quite a soup of where bounds unfortunately.

Typenum nowadays enables arrayvec to use any size however, so that's neat; It's by simply both supporting fixed size arrays (a finite number of trait impls) and GenericArray as the backend (one trait impl)

[clinbr]

With specialization it's possible to define an "Add" as

trait UAdd<R: Unsigned> {
    type Output: Unsigned;
}

default impl<L: Unsigned, R:Unsigned> UAdd<R> for L {
    type Output = UTerm;
}

But now we've run into the problem that we can't prove that the U in Uint<U, B> is :Unsigned. Apparently there were performance reasons for defining UInt the way it was defined?

Of course this wont work for subtraction.

Anyway, I figured this comment should exist in case someone finds it interesting. I've been using a similar trick using specialisation to patch generic-array so that U: Unsigned implies U: ArrayLength<T> for all T. That one seems more promising.

[paholg]

Neat! I figured this would become possible with specialization, but didn't know we were there yet. Will definitely play with it.

But now we've run into the problem that we can't prove that the U in Uint<U, B> is :Unsigned. Apparently there were performance reasons for defining UInt the way it was defined?

Yeah, due to a compiler bug that has since been fixed. So we can put the trait bounds back. While that's technically a breaking change, the documentation is pretty clear that nothing else should ever go there, so I don't see a problem with it.