Making a type level linked list with `typenum` crate

This is similar to this issue, or rather it is a follow-up. Although there is an accepted answer in that issue, I still want to pursue the type level solution, perhaps just for the sake of sharpening my skill in this.


Given any type level unsigned integer from the typenum crate, e.g. typenum::consts::U365, using a type function, get the closest Rust's unsigned integer type to represent it, e.g. U365 -> 365 -> u16, since u8::MAX = 255 < 365.

I tried to do a type level linked list and at each node, it compares if N: typenum::Unsigned (i.e. N is the type level unsigned integer) is lesser than (but not equal) to e.g. typenum::Shleft<U1, U8>, then it returns u8, else it continues to compare N with typenum::Shleft<U1, U16>, ..., U32, U64 and U128 and returns () if it is larger than what is representable by 128 bits.

use core::{marker::PhantomData, ops::Shl};
use typenum::{
    Bit, Cmp, False, IsLess, True, Unsigned, U0, U1, U128, U365, U16, U2, U3, U32, U4, U5, U64, U8,
    B0, B1, U65536, Shleft,

struct Either<L, R>(PhantomData<(L, R)>);

trait If<C: Bit> {
    type Output;

impl<L, R> If<B1> for Either<L, R> {
    type Output = L;

impl<L, R> If<B0> for Either<L, R> {
    type Output = R;

The Either type is the branch and the If is the type function.

If type function works:

fn main() {
    println!("{}", IsLessThan::<U365, Shleft<U1, U16>>::BOOL); // true

Some type aliases to make life easy:

type U1Shl<K> = <U1 as Shl<K>>::Output;

type IsLessThan<M, N> = <M as IsLess<N>>::Output;

Definition of the trait PrivateList:

trait PrivateList<Q: Unsigned> {
    type Next;

And these are its impls for just two types for now, U8 and U16.

impl<N> PrivateList<U8> for N
    N: Unsigned + IsLess<Shleft<U1, U8>> + IsLess<U8>,
    Either<u8, ()>: If<<N as IsLess<Shleft<U1, U8>>>::Output>,
    type Next = <Either::<u8, <N as PrivateList<U16>>::Next> as If::<IsLessThan::<N, Shleft<U1, U8>>>>::Output;

impl<N> PrivateList<U16> for N
    N: Unsigned,
    type Next = ();

The error messages tell me that I have not added trait bounds for N: typenum::consts::U8 but despite adding it, it shows the exact same error messages.


If the compiler suggest a where bound which already exists that would be a bug. Please report it on the rust issue tracker: Issues · rust-lang/rust · GitHub