#Recursive Associated Types

14 messages · Page 1 of 1 (latest)

lean basalt
#

Hey all, I’m trying to create a generic type list like so:

trait List {
type Head;
type Tail;
}

impl<H> List for (H, ()) {
type Head = H;
type Tail = ();
}

impl<H, T: List> List for (H, T) {
type Head = H;
type Tail = (<Self::Tail as List>::Head, <Self::Tail as List>::Tail);
}

So effectively each tail type would recursively get the next tail type as a List until I hit a List that has a unit type tail type. Unfortunately, the compiler errors out with an inability to parse the infinitely recursive type. I know that boxing the recursive type is what would normally be suggested here, but heap allocations are strictly not allowed for my particular use case. Any suggestions on how to encode this kind of recursive type into the type system without the compiler freaking out?

tawdry flame
#

huh. shouldnt it be

impl<H, T: List> List for (H, T) {
    type Head = H;
    type Tail = (T::Head, T::Tail);
}
#

?play

use std::any::type_name;

trait List {
    type Head;
    type Tail;
}

impl<H> List for (H, ()) {
    type Head = H;
    type Tail = ();
}

impl<H, T: List> List for (H, T) {
    type Head = H;
    type Tail = (T::Head, T::Tail);
}

type Foo = (i8, (i16, (i32, (i64, ()))));
type TailOf<L> = <L as List>::Tail;

fn main() {
    println!("{}", type_name::<Foo>());
    println!("{}", type_name::<TailOf<Foo>>());
    println!("{}", type_name::<TailOf<TailOf<Foo>>>());
}
unkempt flowerBOT
# 
(i8, (i16, (i32, (i64, ()))))
(i16, (i32, (i64, ())))
(i32, (i64, ()))```
tawdry flame
#

anyways to answer the question, you shouldnt use Self, that's referring to (H, T), not T

desert shell
#

Why can't it just be:

impl<H, T: List> List for (H, T) {
    type Head = H;
    type Tail = T;
}
lean basalt
#

Thanks all for your input! Yeah I think I was confusing the use of Self in a trait definition vs a trait implementation. I think this will work!

desert shell
lean basalt
#

Are you sure? In the above Impl block for (H, T), wouldn’t self refer to the tuple, not the trait?

desert shell
lean basalt
desert shell
#

It does in fact refer to the tuple, even if it doesn't know that it's a tuple

#

It refers to whatever type implements the trait.

desert shell