Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Demonstrate searching a type-level list in rust
#![allow(dead_code)]
struct True;
struct False;
impl IsEqual<False> for True {type Out=False;}
impl IsEqual<False> for False {type Out=True;}
impl IsEqual<True> for True {type Out=True;}
impl IsEqual<True> for False {type Out=False;}
trait Nat {fn inst()->usize;}
struct Zero;
impl Nat for Zero {fn inst()->usize{0}}
struct Succ<N>(N);
impl<N:Nat> Nat for Succ<N> {fn inst()->usize{1+N::inst()}}
trait Greater<N> {}
impl<N> Greater<Zero> for Succ<N> {}
impl<N1,N2> Greater<Succ<N2>> for Succ<N1> where
N1: Greater<N2>,
{}
trait IsEqual<N> {type Out;}
impl IsEqual<Zero> for Zero {type Out=True;}
impl<N> IsEqual<Zero> for Succ<N> {type Out=False;}
impl<N> IsEqual<Succ<N>> for Zero {type Out=False;}
impl<B,N1,N2> IsEqual<Succ<N2>> for Succ<N1> where
N1: IsEqual<N2,Out=B>,
{type Out=B;}
trait List {}
struct Nil;
impl List for Nil {}
struct Cons<E,L:List>(E,L);
impl<E,L:List> List for Cons<E,L> {}
trait Contains<E,N> {}
impl<E,L:List> Contains<E,Zero> for Cons<E,L> {}
impl<E,F,N,L:List> Contains<E,Succ<N>> for Cons<F,L> where L:Contains<E,N> {}
trait Closest<E> {type D;}
trait CBranch<B,E> {type D;}
impl<D,R,E,F,L:List> Closest<E> for Cons<F,L> where
E:IsEqual<F,Out=R>,
Self:CBranch<R,E,D=D>,
{type D=D;}
impl<E,F,L:List> CBranch<True,E> for Cons<F,L> {type D=Zero;}
impl<E,F,N,L:List> CBranch<False,E> for Cons<F,L> where
L:Closest<E,D=N>,
{type D=Succ<N>;}
fn main() {
fn closest<N:Nat,L:Closest<False,D=N>>(_:L) -> usize {N::inst()}
//let a = Nil;println!("{:?}",closest(a));
let a = Cons(False,Nil);println!("{:?}",closest(a));
//let a = Cons(True,Nil);println!("{:?}",closest(a));
//let a = Cons(True,Cons(True,Nil));println!("{:?}",closest(a));
let a = Cons(True,Cons(False,Nil));println!("{:?}",closest(a));
let a = Cons(False,Cons(True,Nil));println!("{:?}",closest(a));
let a = Cons(False,Cons(False,Nil));println!("{:?}",closest(a));
let a = Cons(True,Cons(True,Cons(False,Cons(True,Cons(False,Nil)))));println!("{:?}",closest(a));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.