Difficulties implementing a const list

Without any direct application, I was wondering how "easy" (as in time required to understand why it works) it is to implement something I would describe as const list (using any nightly features as needed).
What think when saying "const list":

  • Something that can be used as a list
  • Is calculated at compile time
  • And the difficult part: supports basic list operations (returning const list(s))

I know there are some crates out there that implement something similar (slist) but at least the ones I found lack on the third point noted above.

For brevity I'm going to use some Haskell notation :slight_smile:

For example a basic requirement for me under point 3 would be being able to zip two lists: [a] -> [b] -> [(a,b)]

For starters I began something using const generics and arrived at the following:

#![feature(const_generics, const_evaluatable_checked)]
struct List<const L: usize> {
    list: [usize; L],
}
impl<const L: usize> List<L> {
    fn concat<const L2: usize>(self, other: List<L2>) -> List<{ L + L2 }> {
        unimplemented!()
    }
}

which provides const list length but not const list content.
So the obvious next step I thought would be to make the list contents const but that sadly does not compile:

struct List<const L: usize, const C:  [usize; L]> {}

Because const generics are not allowed to depend on each other :frowning:

After hitting this roadblock I thought to myself "well, maybe let's try the more classic algebraic type way". After trying multiple times I always seem to get stuck at fundamental problems like:

  • using an enum List<H,T>{Empty,List(H,T)}: cannot seem to find a way to write the return type as it would depend on the concrete enum variant
  • using struct List<H,T>(H,T) in combination with struct Empty{}: couldn't find a way to properly define a recursion anchor when writing down const fn Zip.

In most cases I end up with something along these lines:

#[derive(Copy, Clone)]
struct List<H, T>(H, T);

//#[derive(Copy, Clone)]
//struct Empty {}

trait ZipList: Copy {
    type Output;
}

//impl ZipList for Empty {
//    type Output = Empty;
//}

impl<H, T> ZipList for List<H, T>
where
    T: ZipList + Copy,
    H: Copy,
{
    type Output = List<(H, H), T::Output>;
}

const fn Zip<H, T>(l1: List<H, T>, l2: List<H, T>) -> <List<H, T> as ZipList>::Output
where
    List<H, T>: ZipList,
{
    List((l1.0, l2.0), Zip(l1.1, l2.1))
}

Which doesn't compile and does not have a recursion anchor.

If anybody could point me in the right direction how something like this can be implemented I would be very thankfull :slight_smile:

The author of frunk has some nice articles about advanced type-level programming in Rust that you might be interested in.

If you treat each type as an individual value instead of a set of values, you can write something like this:

#![feature(min_const_generics)] // or `use::typenum;`

trait ConstVal {
    type RuntimeType;
    const VAL: Self::RuntimeType;
}

#[derive(Copy, Clone, Debug)]
struct List<H, T>(H, T);

impl<H:ConstVal, T:ConstVal> ConstVal for List<H,T> {
    type RuntimeType = List<H::RuntimeType, T::RuntimeType>;
    const VAL: Self::RuntimeType = List(H::VAL, T::VAL);
}

impl<H:ConstVal, T:ConstVal> ConstVal for (H,T) {
    type RuntimeType = (H::RuntimeType, T::RuntimeType);
    const VAL: Self::RuntimeType = (H::VAL, T::VAL);
}

#[derive(Copy, Clone, Debug)]
struct Empty;

impl ConstVal for Empty {
    type RuntimeType = Self;
    const VAL:Self = Empty;
}

trait ZipList<L2>: Copy {
    type Output;
}

impl ZipList<Empty> for Empty {
    type Output = Empty;
}

impl<H1, T1, H2, T2> ZipList<List<H2,T2>> for List<H1, T1>
where
    T1: ZipList<T2> + Copy,
    T2: Copy,
    H1: Copy,
    H2: Copy,
{
    type Output = List<(H1, H2), T1::Output>;
}

#[derive(Copy,Clone,Debug)]
struct USize<const N:usize>;

impl<const N:usize> ConstVal for USize<N> {
    type RuntimeType = usize;
    const VAL: usize = N;
}

macro_rules! get_const {
    ($name:ident = $val:ty) => { const $name: <$val as ConstVal>::RuntimeType = <$val as ConstVal>::VAL; }
}

macro_rules! list {
    () => { Empty };
    ($H:ty $(, $($T:tt)*)?) => { List<$H, list!{$($($T)*)?}> }
}

type Zip<A,B> = <A as ZipList<B>>::Output;

fn main() {
    get_const!{ SEVEN = USize<7> }
    dbg!(SEVEN);

    type L1ty = list![USize<2>, USize<4>];
    get_const!{ L1 = L1ty }
    dbg!(L1);

    get_const!{ LZIP = Zip<L1ty, list![USize<11>, USize<13>]> }
    dbg!(LZIP);
}

(Playground)

1 Like

Thanks a lot for the link and the perfect example :slight_smile:
It will however take some time to get my head around whats happening there and why that works and my attempts did not :smiley:

Have a nice day!