Fixed point for generic data type

[usamoi]

Hello. I want to implement a fixed point for generic data type as below:

pub enum Fun<T> {
    Cons(Box<T>),
    // blablablabla
}

// want to pass Self as generic parameter
type FunSelf = Fun<FunSelf>;

// FunSelf would be become this after monomorphization
pub enum FunSelf {
    Cons(Box<FunSelf>),
    // blablablabla
}

// but that doesn't check
// though I can write this
struct FunSelf(Fun<FunSelf>);
// it seems weird and it brings unbearable noisy in my code

How do I approximately implement it without too many nested structs in Rust?

[Finn]

From what I can tell, recursive types cannot be achieved by anything other than struct or enum. The same issue is present in other languages as well, see Recursive data type, section In type synonyms in Wikipedia.

It might be more favorable for you to state the demanded type this way:

pub enum Fun<T> {
    Cons(Box<T>)
}

struct Rec(FunSelf);

type FunSelf = Fun<Rec>;

[usamoi]

With the feature generic associated types, I can write the following code:

pub trait Proxy {
    type Ref<FakeSelf>;
}

pub enum Fun<P: Proxy> {
    QuoteSelf(Box<P::Ref<Self>>),
    QuoteOther(i32),
}

impl Proxy for () {
    type Ref<S> = S;
}

impl Proxy for ((), ()) {
    type Ref<S> = i32;
}

pub type FunSelf = Fun<()>;
pub type FunOther = Fun<((), ())>;

It checks, but fails when I derive Debug, Clone or any other macros. So it's just a toy and I do not know whether it's because of incomplete feature

[quinedot]

You don't need GAT for this indirection, but it's still not supported by #[derive(Debug)].

You could work around it by manually implementing the traits you need.

[steffahn]

Perhaps not really answering your question, but it might be of interest: Your question made attempt to adapt the examples in the explanation of a generic Fix data type from Haskell

newtype Fix f = Fix (f (Fix f))

that can be found in this answer on SO

Understanding the Fix datatype in Haskell

into Rust.

(Using an approach of Functors in Rust adapting my own earlier toy example for Monads:)

Monads in Rust, with GATs

Hi, greetings to all fellow monad enthusiasts out there, I’ve come across a way to “encode” type constructors with GATs. Here’s a demo for anyone interested. (This is just a proof of concept so far, in particular it isn’t efficient at all with those clones or anything.) In case anyone else has already done something similar, please tell me ^^ // a lot of trait definitions omitted, see playground link below struct Vec_; impl TyCon for Vec_ { type Of<T> = Vec<T>; } impl<T> HasTyCon for Vec<T…

Anyways, here’s the result of this attempt

#![feature(generic_associated_types)]
#![allow(unused)]

use std::{marker::PhantomData, rc::Rc};

#[derive(Debug, Eq, PartialEq)]
struct List<A>(Rc<ListInner<A>>);
#[derive(Debug, Eq, PartialEq)]
enum ListInner<A> {
    Nil,
    Cons(Rc<A>, List<A>),
}
impl<A> List<A> {
    fn cons(x: Rc<A>, xs: List<A>) -> Self {
        Self(Rc::new(ListInner::Cons(x, xs)))
    }
    fn nil() -> Self {
        Self(Rc::new(ListInner::Nil))
    }
}

#[derive(Debug, Eq, PartialEq)]
enum Cons<A, Recur> {
    Nil,
    Cons(Rc<A>, Recur),
}

trait TyCon {
    type Of<T>: HasTyCon<Param = T, GetTyCon = Self>;
}
trait TyConAccepting<T>: TyCon {
    type Applied;
}
impl<F: TyCon + ?Sized, T> TyConAccepting<T> for F {
    type Applied = Self::Of<T>;
}
trait HasTyCon {
    type Param;
    type GetTyCon: TyConAccepting<Self::Param, Applied = Self>;
}
trait HasTyConExt: HasTyCon + Sized {
    fn into_con_ty(self) -> <Self::GetTyCon as TyCon>::Of<Self::Param> {
        fn identity<F: TyCon, T>(x: <F as TyConAccepting<T>>::Applied) -> F::Of<T> {
            x
        }
        identity::<Self::GetTyCon, _>(self)
    }
    fn as_con_ty(&self) -> &<Self::GetTyCon as TyCon>::Of<Self::Param> {
        fn identity<F: TyCon, T>(x: &<F as TyConAccepting<T>>::Applied) -> &F::Of<T> {
            x
        }
        identity::<Self::GetTyCon, _>(self)
    }
    fn as_con_ty_mut(&mut self) -> &mut <Self::GetTyCon as TyCon>::Of<Self::Param> {
        fn identity<F: TyCon, T>(x: &mut <F as TyConAccepting<T>>::Applied) -> &mut F::Of<T> {
            x
        }
        identity::<Self::GetTyCon, _>(self)
    }

    fn from_con_ty(this: <Self::GetTyCon as TyCon>::Of<Self::Param>) -> Self {
        fn identity<F: TyCon, T>(x: F::Of<T>) -> <F as TyConAccepting<T>>::Applied {
            x
        }
        identity::<Self::GetTyCon, _>(this)
    }
}
impl<T: HasTyCon> HasTyConExt for T {}

struct Fix<F: TyCon>(Rc<F::Of<Fix<F>>>);
impl<F: TyCon> Fix<F> {
    fn new(x: impl HasTyCon<GetTyCon = F, Param = Fix<F>>) -> Self {
        Fix(Rc::new(x.into_con_ty()))
    }
}

struct Toy<A>(Rc<ToyInner<A>>);
impl<A> Toy<A> {
    fn new(x: ToyInner<A>) -> Self {
        Self(Rc::new(x))
    }
    fn output(a: Rc<A>, next: Toy<A>) -> Self {
        Self::new(ToyInner::Output(a, next))
    }
    fn bell(next: Toy<A>) -> Self {
        Self::new(ToyInner::Bell(next))
    }
    fn done() -> Self {
        Self::new(ToyInner::Done)
    }
}
enum ToyInner<A> {
    Output(Rc<A>, Toy<A>),
    Bell(Toy<A>),
    Done,
}

enum ToyStep<A, Recur> {
    Output(Rc<A>, Recur),
    Bell(Recur),
    Done,
}

struct ToyStep_<A>(PhantomData<A>);
impl<A> TyCon for ToyStep_<A> {
    type Of<Recur> = ToyStep<A, Recur>;
}

impl<A, Recur> HasTyCon for ToyStep<A, Recur> {
    type Param = Recur;
    type GetTyCon = ToyStep_<A>;
}

impl<A> Toy<A> {
    fn to_step(&self) -> Fix<ToyStep_<A>> {
        match &*self.0 {
            ToyInner::Output(a, next) => Fix::new(ToyStep::Output(a.clone(), next.to_step())),
            ToyInner::Bell(next) => Fix::new(ToyStep::Bell(next.to_step())),
            ToyInner::Done => Fix::new(ToyStep::Done),
        }
    }
    fn from_step(arg: &Fix<ToyStep_<A>>) -> Self {
        match &*arg.0 {
            ToyStep::Output(a, next) => Self::output(a.clone(), Self::from_step(next)),
            ToyStep::Bell(next) => Self::bell(Self::from_step(next)),
            ToyStep::Done => Self::done(),
        }
    }
}

trait Functor: TyCon + Sized {
    fn fmap<A, B, F: Fn(&A) -> B>(x: &Self::Of<A>, f: F) -> Self::Of<B>;
}

trait FunctorVal: HasTyCon
where
    Self::GetTyCon: Functor,
{
    fn fmap<B, F: Fn(&Self::Param) -> B>(&self, f: F) -> <Self::GetTyCon as TyCon>::Of<B>;
}
impl<M: HasTyCon> FunctorVal for M
where
    M::GetTyCon: Functor,
{
    fn fmap<B, F: Fn(&Self::Param) -> B>(&self, f: F) -> <Self::GetTyCon as TyCon>::Of<B> {
        Self::GetTyCon::fmap(self.as_con_ty(), f)
    }
}

fn unwrap<K, F: Functor>(f: impl Copy + Fn(F::Of<K>) -> K, n: &Fix<F>) -> K {
    f(n.0.fmap(|n| unwrap(f, n)))
}

fn get_length<A>(arg: Cons<A, usize>) -> usize {
    match arg {
        Cons::Nil => 0,
        Cons::Cons(_, len) => len + 1,
    }
}

struct Cons_<A>(PhantomData<A>);
impl<A> TyCon for Cons_<A> {
    type Of<Recur> = Cons<A, Recur>;
}
impl<A, Recur> HasTyCon for Cons<A, Recur> {
    type Param = Recur;
    type GetTyCon = Cons_<A>;
}

fn length<A>(arg: &Fix<Cons_<A>>) -> usize {
    unwrap(get_length, arg)
}

impl<A> Functor for Cons_<A> {
    fn fmap<R, S, F: Fn(&R) -> S>(x: &Self::Of<R>, f: F) -> Self::Of<S> {
        use Cons as C;
        match &*x {
            C::Cons(x, r) => C::Cons(x.clone(), f(r)),
            C::Nil => Cons::Nil,
        }
    }
}

impl<A> ToyStep<A, List<A>> {
    fn get_outputs(self) -> List<A> {
        use ToyStep::*;
        match self {
            Output(b, bs) => List::cons(b, bs),
            Bell(bs) => bs,
            Done => List::nil(),
        }
    }
}

fn outputs<A>(arg: &Fix<ToyStep_<A>>) -> List<A> {
    unwrap(ToyStep::get_outputs, arg)
}

impl<A> Functor for ToyStep_<A> {
    fn fmap<R, S, F: Fn(&R) -> S>(x: &Self::Of<R>, f: F) -> Self::Of<S> {
        use ToyStep::*;
        match x {
            Output(a, r) => Output(a.clone(), f(r)),
            Bell(r) => Bell(f(r)),
            Done => Done,
        }
    }
}

fn main() {
    let toy: Toy<&str> = Toy::output(
        "hi".into(),
        Toy::bell(Toy::output("world".into(), Toy::done())),
    );
    dbg!(outputs(&toy.to_step()));
}

playground

---

One thing I noticed was the need to add a layer of indirection in defining Fix

struct Fix<F: TyCon>(Rc<F::Of<Fix<F>>>);
// would work with `Box`, too

// using `Rc` everywhere for making adapting code
// from a pure functional language easier

otherwise, the compiler isn’t happy because F::Of<A> might contain an A without indirection and there isn’t a good way to restrict a GAT to disallow this. (The “not good” way I’ve found would be to require that F::Of<A> is supposed to support unsized A while being Sized itself, but that’s way stronger of a requirement than necessary.)