Design patterns for composability with traits (i.e. typeclasses)?

help
119

I think I have understood your proposal now, it took me a while to untangle all the related issues, and I think we were both coming from quite different starting points. Whilst I think your proposal is nice, it is not for me, because performance and monomorphisation are critical things for me. That means the addition of the hash lookup and the lack of monomorphisation, and the requirement for GC, as well as the emphasis on immutability would not work for the kind of progamming language I am interested in. I would definitely be interested to keep up to date with your work, as I think it has a legitimate niche where it could succeed. I would target a replacement for Scheme.

So although I am interested in this, and am happy to help, act as a sounding board, if a slightly dense one :slight_smile: my own work will continue down a slightly different route. I am interested in the expression problem part of this, but having looked around I have translated a solution from Haskell to Rust, and here is the code

mod a { // define algebra
    #[derive(Clone)]
    pub struct Lit(pub i32);
    
    #[derive(Clone)]
    pub struct Add<L, R>(pub L, pub R);

    pub trait Eval {
        fn eval(&self) -> i32;
    }

    impl Eval for Lit {
        fn eval(&self) -> i32 {
            self.0
        }
    }

    impl<L, R> Eval for Add<L, R>
    where L : Eval, R : Eval {
        fn eval(&self) -> i32 {
             self.0.eval() + self.1.eval()
        }
    }
}

mod b { // Add a new function over the datatype
    use a::{Lit, Add};
    
    pub trait PPrint {
        fn pprint(&self) -> String;
    }
    
    impl PPrint for Lit {
        fn pprint(&self) -> String {
            self.0.to_string()
        }
    }
    
    impl<'a, L, R> PPrint for Add<L, R>
    where L : PPrint + 'a, R : PPrint + 'a {
        fn pprint(&self) -> String {
            let mut s = "(".to_string();
            s.push_str(&self.0.pprint());
            s.push_str(" + ");
            s.push_str(&self.1.pprint());
            s.push_str(")");
            s
        }
    }
}

mod c { // Add new datatype
    use a::Eval;
    use b::PPrint;
    
    #[derive(Clone)]
    pub struct Mul<L, R>(pub L, pub R);
    
    impl<L, R> Eval for Mul<L, R>
    where L : Eval, R : Eval {
        fn eval(&self) -> i32 {
            self.0.eval() * self.0.eval()
        }
    }
    
    impl<L, R> PPrint for Mul<L, R>
    where L : PPrint, R : PPrint {
        fn pprint(&self) -> String {
            let mut s = "(".to_string();
            s.push_str(&self.0.pprint());
            s.push_str(" * ");
            s.push_str(&self.1.pprint());
            s.push_str(")");
            s
        }
    }
}

fn main() {
    use a::{Eval, Lit, Add};
    use b::PPrint;
    use c::Mul;
    
    let three_plus5 = Add(Lit(3), Lit(5));
    let three_plus5_times7 = Mul(three_plus5.clone(), Lit(7));
    println!("{} = {}", three_plus5.pprint(), three_plus5.eval());
    println!("{} = {}", three_plus5_times7.pprint(), three_plus5_times7.eval());
    
}

This doesn't solve all the problems you are trying to solve, and it is not meant to, but it does seem a reasonable solution to the expression problem implementable in Rust as it is, the trick is to treat the collection object as an expression grammar rather than a simple type or enum. To implement a heterogeneous collection we would use the same technique as in the HList paper, and create a 'Cons' datatype, to represent a list constructor, implemented in the same way as 'Add' or 'Mul'.