# Simultaneous left and right recursive data structure

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?

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.

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.