Generics of Generic types

Question

I am about to start learning Rust after programming in C++. I am unsure how to create a function (or anything else generic) that takes a generic type as its template argument.

I have tried to compile the following code:

trait Monad {
    fn singleton<T>(t: T) -> Self<T>;
    fn compact<T>(mmt: Self<Self<T>>) -> Self<T>;
}

fn id<F>(fi: F<i8>) -> F<i8> {return fi;}

however this spits out a bunch of type argument not allowed errors.

In C++20 I would write:

template<typename<typename> M>
concept monad = requires(...){...};

template<typename<typename> F>
F<std::byte> id(F<std::byte> fi) {return fi;}

How would I implement this functionality in Rust?

Answer 1

Template template parameters are a limited form of higher-kinded types.

Rust also has a limited form of higher-kinded types in the form of "generic associated types". These are available on the nightly. Concretely, the Monad example might look like:

#![feature(generic_associated_types)]

trait Monad {
    type Type<T>;
    fn singleton<T>(t: T) -> Self::Type<T>;
    fn compact<T>(mmt: Self::Type<Self::Type<T>>) -> Self::Type<T>;
}

struct Vector;

impl Monad for Vector {
    type Type<T> = Vec<T>;
    fn singleton<T>(t: T) -> Self::Type<T> {
        vec![t]
    }
    fn compact<T>(mmt: Self::Type<Self::Type<T>>) -> Self::Type<T> {
        mmt.into_iter().flatten().collect()
    }
}

playground

In a trait, Self is always a concrete type and not a type constructor. Because only concrete types satisfy traits. That's why Self<T> is not accepted.

To compare and contrast with C++, in Rust you cannot refer to Vec without its type parameter as a type constructor. std::vector itself is nameable in C++. Therefore, we have to use a stand-in Vector for it in Rust. Also, our Rust implementation uses an unstable language feature.

On the other hand, you'd struggle to finish writing that monad concept in C++. A template template parameter cannot be applied to any type. The type constructor is partial, and that partiality is implicit. A reasonable requirement for monad might be that it can be instantiated with any std::movable type and that the functions are defined for std::movable type parameters. That is not expressible in C++.

So, in C++, you might write something like this:

struct movable {
    movable() = delete;
    movable(const movable&) = delete;
    movable(movable&&) noexcept = default;
    movable& operator=(const movable&) = delete;
    movable& operator=(movable&&) noexcept = default;
    ~movable() = default;
};

template<template<typename> typename M>
struct type {};

template<template<typename> typename M>
concept monad = requires {
    { singleton(type<M>{}, movable{}) } -> std::same_as<M<movable>>;
    // compact is similar
};

In C++, you can't say a constraint holds for instantiations at all types of a certain shape (e.g. std::movable). So you create a type that is of that shape and nothing more, and require that the constraint hold at just that one instantiation. People have taken to calling these types "archetypes". You hope that there are no specializations, overloads, or other things that might stop this satisfaction from generalizing to all types of that shape.

Then, you have a choice about where the functions live. Template template parameters cannot have member functions, so you either put them in a particular instantiation (e.g. M<T> is constructible from T) or as a free function. Using member functions has downsides, because it cannot be externally implemented. With a free function, you need a way to identify the monad, so you end up wrapping up the template template parameter in a stand-in type as well.

These are interesting to compare.

Answer 2

These are called Higher Kinded Types or Type Constructors.

Rust currently doesn't have those, with two caveats to that statement.

1. There are soon going to be such things as generic associated types, which are similar, but not quite the same:

   trait Foo {
       type OutputCollection<T>;
       fn get_collection<T>(&self) -> Self::OutputCollection<T>;
   }
   

   Read more here and here.

2. You can kind of emulate them using helper traits, but it's not nice looking:

   trait ContainerHelper<Container> {
       type Container;
   }
   
   struct VecContainer;
   
   impl<T> ContainerHelper<VecContainer> for T {
       type Container = Vec<T>;
   }
   
   trait Foo {
       fn get_collection<T, Container>(&self) -> 
           <T as ContainerHelper<Container>>::Container
       where
           T: ContainerHelper<Container>;
   }