Created
September 30, 2019 10:27
-
-
Save jerry73204/364c4b61d884c1150807cdcc9357890d to your computer and use it in GitHub Desktop.
Rusts trait recursion test: trait recursion vs functor trait recursion
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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>; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Overview
The gist defines a typed list trait named
TList
. TheCons
type is node of list, andNil
is end of list.The auxiliary
Counter
trait is used for trait recursion. TheCurrent
is end of recursion, whileNext
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 onNil
andCons
respectively and it works.Second strategy
The second way is less straightforward, but more general. It defines a
Functor
trait. Any types withFunctor
trait is regarded as a type operator. Then we defineInsertFunctor
withFunctor
to insert new key toTList
. Also, it implements onNil
andCons
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.