Rusts trait recursion test: trait recursion vs functor trait recursion

rust_trait_recursion_test.rs

use std::marker::PhantomData;

/* Counter def, used to distinguish termination and non-termination step */

/// counter trait
pub trait Counter {}

/// End of counter
pub struct Current;

impl Counter for Current {}

/// Intermediate step of counter.
pub struct Next<Cnt>
where
    Cnt: Counter,
{
    _phantom: PhantomData<Cnt>,
}

impl<Cnt> Counter for Next<Cnt> where Cnt: Counter {}

/* Type list def */

/// Typed list trait.
pub trait TList {}

/// End of list.
pub struct Nil;

impl TList for Nil {}

/// Intermediate node of list with key.
pub struct Cons<Key, Tail>
where
    Tail: TList,
{
    _phantom: PhantomData<(Key, Tail)>,
}

impl<Key, Tail> TList for Cons<Key, Tail> where Tail: TList {}

/* First strategy: use recursive trait. It works eventually. */

/// Insert trait.
pub trait Insert<NewKey, Target, Cnt>
where
    Cnt: Counter,
    Self: TList,
    Self::Output: TList,
{
    type Output;
}

/// Termination step.
impl<NewKey, Target, Tail> Insert<NewKey, Target, Current> for Cons<Target, Tail>
where
    Tail: TList,
{
    type Output = Cons<Target, Cons<NewKey, Tail>>;
}

/// Non-termination step.
impl<NewKey, Target, Index, NonTarget, Tail> Insert<NewKey, Target, Next<Index>>
    for Cons<NonTarget, Tail>
where
    Tail: TList + Insert<NewKey, Target, Index>,
    Index: Counter,
{
    type Output = Cons<NonTarget, <Tail as Insert<NewKey, Target, Index>>::Output>;
}

/* Functor def */

/// Types implementing this trait is _appliable_.
pub trait Functor<Input> {
    type Output;
}

/* Second strategy: recursive functor impl. It leads to overflow evaluation error. */

/// A functor that inserts a new key after target in list.
pub struct InsertFunctor<NewKey, Target, Index>
where
    Index: Counter,
{
    _phantom: PhantomData<(NewKey, Target, Index)>,
}

/// Termination of functor.
impl<Target, Tail, NewKey> Functor<Cons<Target, Tail>> for InsertFunctor<NewKey, Target, Current>
where
    Tail: TList,
{
    type Output = Cons<Target, Cons<NewKey, Tail>>;
}

/// Non-termination of functor.
impl<NonTarget, Tail, NewKey, Target, Index> Functor<Cons<NonTarget, Tail>>
    for InsertFunctor<NewKey, Target, Next<Index>>
where
    Tail: TList,
    Index: Counter,
    InsertFunctor<NewKey, Target, Index>: Functor<Tail>,
    <InsertFunctor<NewKey, Target, Index> as Functor<Tail>>::Output: TList,
{
    type Output = Cons<NonTarget, <InsertFunctor<NewKey, Target, Index> as Functor<Tail>>::Output>;
}

Overview

The gist defines a typed list trait named TList. The Cons type is node of list, and Nil is end of list.
The auxiliary Counter trait is used for trait recursion. The Current is end of recursion, while Next is recursion step.

It attempts to insert a new key after some target key in TList. Here comes two strategies.

First strategy

The first strategy is to define a type operator trait called Insert. It implements on Nil and Cons respectively and it works.

Second strategy

The second way is less straightforward, but more general. It defines a Functor trait. Any types with Functor trait is regarded as a type operator. Then we define InsertFunctor with Functor to insert new key to TList. Also, it implements on Nil and Cons respectively. However, it leads to overflow evaluation error.

Thoughts

Both strategies have recursion calls with same set of generics. However, the compiler fails to find the termination step with functor indirection.

<Tail as Insert<NewKey, Target, Index>>::Output
<InsertFunctor<NewKey, Target, Index> as Functor<Tail>>::Output