One-of-some types for Parametric Polymorphism (a very small subset of union typing)


#1

Sometimes I have to define functions and call them generically on just few types, like this gcd that I call with u16, u32 and u64 only:

fn gcd_u16(mut u: u16, mut v: u16) -> u16 {...}
fn gcd_u32(mut u: u32, mut v: u32) -> u32 {...}
fn gcd_u64(mut u: u64, mut v: u64) -> u64 {...}

Sometimes macros are used to generate the various functions in a more DRY way:

macro_rules! gcd_generator {
    ($name:ident, $t:ty) => {
        fn $name(mut u: $t, mut v: $t) -> $t {
            if v == 0 { return u; }
            loop {
                u %= v;
                if u == 0 { return v; }
                v %= u;
                if v == 0 { return u; }
            }
        }
    };
}

gcd_generator!{gcd_u16, u16}
gcd_generator!{gcd_u32, u32}
gcd_generator!{gcd_u64, u64}

Generics allow me to write only a function (and it gets instantiated on just the types that I actually use, unlike the macro):

fn gcd<T>(mut u: T, mut v: T) -> T
where T: PartialEq + RemAssign + Copy + Clone + From<u8> {
    if v == 0.into() { return u; }
    loop {
        u %= v;
        if u == 0.into() { return v; }
        v %= u;
        if v == 0.into() { return u; }
    }
}

The num_traits crate allows to write that function in a less hacky and nicer way:

extern crate num_traits;
use num_traits::Unsigned;
use std::ops::RemAssign;

fn gcd<T>(mut u: T, mut v: T) -> T
where T: Unsigned + RemAssign + Copy {
    if v == T::zero() { return u; }
    loop {
        u %= v;
        if u == T::zero() { return v; }
        v %= u;
        if v == T::zero() { return u; }
    }
}

But a simpler solution could be to specify only few allowed types:

fn gcd<U>(mut u: U, mut v: U) -> U {
where U: u16 | u32 | u64 {
    if v == 0 { return u; }
    loop {
        u %= v;
        if u == 0 { return v; }
        v %= u;
        if v == 0 { return u; }
    }
}

Something similar could work with const generics too:

fn foo<const usize N = 5 | 10>(a: &[u32; N]) -> u32 {
    // ...
}

Unlike most Rust features this is quite specific.


#2

That seems like “Junction Types” which is really the same thing as “Sum Types”/“Enums”? To me a “Junction Type” is just an anonymous Enum/Sum-Type.


#3

The use case I’ve shown here is very specific, and for me rather handy, but the syntax I’ve used should be compatible with an optional successive generalization to Junction Types.


#4

First, the thread title could be a bit more clear, cause the answer to the question is just: “Yes, Rust has bounded parametric polymorphism, what about it?”.

About the issue itself, I believe this could alternatively be modeled with closed traits (think of closed type families) where you define all the instances up front.

Otherwise, I think you need some form of type equality constraints and a way to say “either this constraint or that constraint” In other words, we can interpret where U: u16 | u32 | u64 as where Oneof(U == u16, U == u32, U == u64).


#5

Right, it’s another way to bound it :slight_smile: This thread title is not precise.

Right, I think that’s what Junction Types are in some recent languages. Here I’ve followed the Rust strategy of introducing features in a very limited but useful way, and leave both syntax and semantics open to successive extensions if they are desired. That “or” means that inside that gcd function you are allowed to use only the methods and associated constants shared by all the given types.


#6

What I was trying to say is: Can we rename it to make it more clear? :stuck_out_tongue:

This is a bit tricky… If you are allowed to use any inherent item (fn, const, and possibly soon types) then you get pretty much structural typing where you identify the methods to be the same if they have the signature (name, quantified variables in right order, input arguments in order, and the return type). This would not be the case with trait items where you have nominal typing instead due to explicit implementations of traits. I believe the only other place where Rust has structural typing right now is with tuples (for obvious reasons…) and it would be quite an expansion of structural typing to add it to bounds.


#7

I’ve renamed it in a quite long way.

I understand, it’s a significant shift for Rust generics. I am not qualified to judge if this handy feature is worth implementing and having in Rust.


#8

It might help to have some sort of macro short-hand for implementing multiple items at once. I know that’s something I often do, and a common usecase for macros.

macro_for_each!  {
    where $U in [u16, u32, u64]:
fn gcd_$U(mut u: $U, mut v: $U) -> $U {
    if v == 0 { return u; }
    loop {
        u %= v;
        if u == 0 { return v; }
        v %= u;
        if v == 0 { return u; }
    }
}
}