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
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
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 withstruct Empty{}
: couldn't find a way to properly define a recursion anchor when writing downconst 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