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

## Objective

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

Playground

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

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.