Simultaneous left and right recursive data structure

[grom]

Let's say I want to make an implementation where I can match a left recursive tuple pattern (note the min_specialization feature)

#![feature(min_specialization)]
impl<T> Trait for (T, StateC) // default
impl<T> Trait for (StateA, (T, (StateC))

This works fine for (StateA, (StateB, (StateC))).

Now let's say I want to also match this right recursive tuple pattern.

#![feature(min_specialization)]
impl<T> Trait for (StateA, T) // default
impl<T> Trait for (((StateA), T) StateC))

I would need to make this tuple pattern (((StateA), StateB), StateC).

But how do I use both impls simultaneously where I only need to construct one tuple pattern? That is, if I make one data structure such as (StateA, StateB, StateC) but doesn't have to be a tuple, how can I make two implementation where one impl can matche the left recursive form and the second impl match the right recursive form? This doesn't seem immediately possible, obviously. But are there any tricks anyone can think of?

[grom]

The only thing I can come up with is to make both tuple patterns and wrap them together

struct LeftRight<T>(T);
LeftRight(
    (StateA, (StateB, (StateC))),
    (((StateA), StateB), StateC)
);

Now when I make the impl I can match both forms

impl<T> Trait for LeftRight<(T, StateC), (StateA, T)>

But now I am duplicating the data structure every time I make it. So not thrilled about this solution.