Convert type-level binary tree of 2-tuples to left-leaning

1

I have a generic type struct A<T>(T); and a tree of tuple types which can only contain A<T>, (), or pairs made out of these. So I'll have types like:

()
((), ())
(A<u32>, ())
((), ((), A<String>))
((A<f64>, A<i64>), A<char>)
((), (((), (((), A<bool>), ())), A<f32>))

Question #1: I would like a type-level function for converting these to a left-leaning (or right-leaning, it doesn't matter) tree, effectively a cons list, such that the results of converting the above types line-by-line should be:

()
((), ())
(A<u32>, ())
((), ((), A<String>))
(A<f64>, (A<i64>, A<char>))
((), ((), ((), (A<bool>, ((), A<f32>)))))

Question #2: Preferably, I would also like to filter out any units from the list (except possibly for the last one denoting the "nil" tail). So, after applying this filter, the types would become:

()
()
A<u32> or (A<u32>, ())
A<String> or (A<String>, ())
(A<bool>, A<f32>) or (A<bool>, (A<f32>, ()))
(A<f64>, (A<i64>, A<char>)) or (A<f64>, (A<i64>, (A<char>, ())))

Is something like this possible? I have made several unsuccessful attempts at #1, but I don't seem to be able to avoid sending the trait solver into infinite recursion.

2

Question 1:

trait Concat<Tail> {
    type Out;
    fn concat(self, _:Tail)->Self::Out;
}

impl<Tail> Concat<Tail> for EOL {
    type Out = Tail;
    fn concat(self, t:Tail)->Self::Out {t}
}

impl<A,B,Tail> Concat<Tail> for (A,B)
where B:Concat<Tail> {
    type Out = (A, B::Out);
    fn concat(self, t:Tail)->Self::Out {
        let (a,b) = self;
        (a, b.concat(t))
    }
}

trait Flatten {
    type Out;
    fn flatten(self)->Self::Out;
}

impl<T> Flatten for A<T> {
    type Out = (Self, EOL);
    fn flatten(self)->Self::Out {
        (self, EOL)
    }
}

impl Flatten for () {
    type Out = ((), EOL);
    fn flatten(self)->Self::Out {
        (self, EOL)
    }
}

impl<A,B> Flatten for (A,B)
where A:Flatten, B:Flatten, A::Out: Concat<B::Out> {
    type Out = <A::Out as Concat<B::Out>>::Out;
    fn flatten(self)->Self::Out {
        let (a,b) = self;
        a.flatten().concat(b.flatten())
    }
}
4 Likes
3

Very neat, thanks!

4

And then, to filter the list: Playground

// ===================

struct Keep;
struct Discard;

trait Predicate {
    type Out;
}

impl Predicate for () {
    type Out = Discard;
}

impl<T> Predicate for A<T> {
    type Out = Keep;
}

trait Filter {
    type Out;
    fn filter(self)->Self::Out;
}

impl Filter for EOL {
    type Out = EOL;
    fn filter(self)->Self::Out { EOL }
}

impl<A,B> Filter for (A,B)
where
    A:Predicate,
    A::Out: FilterStep<Self>
{
    type Out = <A::Out as FilterStep<Self>>::Out;
    fn filter(self)->Self::Out {
        <A::Out as FilterStep<Self>>::filter(self)
    }
}

trait FilterStep<List> {
    type Out;
    fn filter(_:List)->Self::Out;
}

impl<A,B> FilterStep<(A,B)> for Keep
where B:Filter {
    type Out = (A, B::Out);
    fn filter((a,b):(A,B))->Self::Out {
        (a, b.filter())
    }
}

impl<A,B> FilterStep<(A,B)> for Discard
where B:Filter {
    type Out = B::Out;
    fn filter((_,b):(A,B))->Self::Out {
        b.filter()
    }
}

(You could probably get away with implementing FilterStep directly for A and (); I didn't try it.)

2 Likes
5

And, finally, a macro to implement Flatten for larger tuples:

macro_rules! impl_tuple_flatten {
    {$x:ident} => {};
    {$h:ident $($t:ident)+} => {
        impl<Head,$h,$($t,)+> Flatten for (Head,$h,$($t,)+)
            where (Head,($h,$($t,)+)): Flatten
        {
            type Out = <(Head,($h,$($t,)+)) as Flatten>::Out;
            fn flatten(self)->Self::Out {
                #[allow(non_snake_case)]
                let (Head,$h,$($t,)+) = self;
                (Head,($h,$($t,)+)).flatten()
            }
        }
        impl_tuple_flatten!{ $($t)+ }
    }
}

impl_tuple_flatten! { B C D E F G H I J K L M N O P Q }

Playground

2 Likes
6

That's pretty nice, too. Fortunately, in my use case, I can completely get away with simulating N-tuples by N nested 2-tuples.

Furthermore, I simplified the filtering code by relying on the fact that I have only A's and ()'s: Playground

struct A<T>(T);

struct Nil;

trait Filter {
    type Out;
    
    fn filter(self) -> Self::Out;
}

impl Filter for Nil {
    type Out = Nil;
    
    fn filter(self) -> Self::Out { Nil }
}

impl<Tail> Filter for ((), Tail)
    where Tail: Filter
{
    type Out = Tail::Out;
    
    fn filter(self) -> Self::Out {
        self.1.filter()
    }
}

impl<T, Tail> Filter for (A<T>, Tail)
    where Tail: Filter
{
    type Out = (A<T>, Tail::Out);
    
    fn filter(self) -> Self::Out {
        (self.0, self.1.filter())
    }
}
1 Like
7

That makes sense. Last time I wrote code like this, I was making it generic over several predicate functions. I guess I just fell back on old habits.

1 Like
8

Well, I'm definitely saving your version because it's strictly more general, so it might very well come handy in the future.

9

I gave this (in particular Question 2) a go, too (without looking at previous comments while implementing this) and I guess my approach is a bit different.

This is what I got so far as proof of concept. Next step would be to add the methods to the traits.

trait PushLeftTo<List> {
    type Pushed;
    //fn push_left_to(self, l: List) -> Self::Pushed;
}

pub struct A<T>(pub T);

impl PushLeftTo<()> for () {
    type Pushed = ();
}
impl<T> PushLeftTo<()> for A<T> {
    type Pushed = A<T>;
}
impl<S> PushLeftTo<A<S>> for () {
    type Pushed = A<S>;
}
impl<S, T> PushLeftTo<A<S>> for A<T> {
    type Pushed = (A<T>, A<S>);
}
impl<X, Y> PushLeftTo<(X, Y)> for () {
    type Pushed = (X, Y);
}
impl<X, Y, T> PushLeftTo<(X, Y)> for A<T> {
    type Pushed = (A<T>, (X, Y));
}

trait SplitTupleLeftPushableTo<List> {
    type Init: PushLeftTo<<Self::Last as PushLeftTo<List>>::Pushed>;
    type Last: PushLeftTo<List>;
    //fn split_tuple(self) -> (Self::Init, Self::Last);
}

impl<Tup, List> PushLeftTo<List> for Tup
where
    Tup: SplitTupleLeftPushableTo<List>,
{
    type Pushed = <<Self as SplitTupleLeftPushableTo<List>>::Init as PushLeftTo<
        <<Self as SplitTupleLeftPushableTo<List>>::Last as PushLeftTo<List>>::Pushed,
    >>::Pushed;
}

macro_rules! split_tuple {
    ($Last:ident $(, $($T:ident),+$(,)?)?) => {
        impl<$($($T,)+)? $Last, List> SplitTupleLeftPushableTo<List> for ($($($T,)+)? $Last,)
        where
            $Last: PushLeftTo<List>,
            ($($($T,)+)?): PushLeftTo<$Last::Pushed>,
        {
            type Init = ($($($T,)+)?);
            type Last = $Last;
        }
    }
}

split_tuple!(T1);
split_tuple!(T2, T1);
split_tuple!(T3, T1, T2);
split_tuple!(T4, T1, T2, T3);
split_tuple!(T5, T1, T2, T3, T4);
split_tuple!(T6, T1, T2, T3, T4, T5);
split_tuple!(T7, T1, T2, T3, T4, T5, T6);
split_tuple!(T8, T1, T2, T3, T4, T5, T6, T7);

trait IntoRightLeaning {
    type Output;
    //fn into_right_leaning(self) -> Self::Output;
}

impl<T> IntoRightLeaning for T
where T: PushLeftTo<()> {
    type Output = T::Pushed;
}

/*
()
((), ())
(A<u32>, ())
((), ((), A<String>))
((A<f64>, A<i64>), A<char>)
((), (((), (((), A<bool>), ())), A<f32>))
*/

fn main() {
    println!("Hello, world!");
    macro_rules! type_for {
        ($t:ty) => {
            println!("{}", std::any::type_name::<<$t as IntoRightLeaning>::Output>());
        }
    }
    type_for!(());
    type_for!(((), ()));
    type_for!((A<u32>, ()));
    type_for!(((), ((), A<String>)));
    type_for!(((A<f64>, A<i64>), A<char>));
    type_for!(((), (((), (((), A<bool>), ())), A<f32>)));
}


Hello, world!
()
()
crate_name::A<u32>
crate_name::A<alloc::string::String>
(crate_name::A<f64>, (crate_name::A<i64>, crate_name::A<char>))
(crate_name::A<bool>, crate_name::A<f32>)

Edit: And here’s the missing methods added: Rust Playground

Edit2: Simplified by removing support for longer tuples: Rust Playground

2 Likes
10

Here's the list-filtering implementation my embedded lisp interpreter uses. It's pretty similar to what I posted above, except that it builds two lists instead of throwing away any of the list elements. It would need to be retooled a bit to be used elsewhere, but it's mostly plain Rust:

pub trait CollatedBy<Test> {
    type Passed;
    type Failed;
    fn collate(self)->(Self::Passed, Self::Failed);
}

impl<T> CollatedBy<T> for HNil {
    type Passed = HNil;
    type Failed = HNil;
    fn collate(self)->(Self::Passed, Self::Failed) { (HNil, HNil) }
}

impl<H,T,Test,Step> CollatedBy<Test> for HCons<H,T>
where sexpr!{Test, @H}: Eval<Result = Step>,
      Step: CollateStep<Test, H, T>
{
    type Passed = Step::Passed;
    type Failed = Step::Failed;
    fn collate(self)->(Self::Passed, Self::Failed) {
        Step::collate_step(self.head, self.tail)
    }
}

pub trait CollateStep<Test, H, T> {
    type Passed;
    type Failed;
    fn collate_step(h:H, t:T)->(Self::Passed, Self::Failed);
}

impl<Test, H, T> CollateStep<Test, H, T> for typenum::True
where T:CollatedBy<Test> {
    type Passed = HCons<H, T::Passed>;
    type Failed = T::Failed;
    fn collate_step(h:H, t:T)->(Self::Passed, Self::Failed) {
        let (pass, fail) = t.collate();
        (sexpr_val!{h; pass}, fail)
    }
}

impl<Test, H, T> CollateStep<Test, H, T> for typenum::False
where T:CollatedBy<Test> {
    type Passed = T::Passed;
    type Failed = HCons<H, T::Failed>;
    fn collate_step(h:H, t:T)->(Self::Passed, Self::Failed) {
        let (pass, fail) = t.collate();
        (pass, sexpr_val!{h; fail})
    }
}
1 Like
11

What I particularly like about all of these solutions is that you can just write the types first, without actually writing the methods, then perform the reification after the fact, if needed (I didn't even need that in my case). I think this is a beautiful instance of the Curry-Howard correspondence.

3 Likes
12

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.