Exploring the power of traits and associated types using a HKT trait definition

hkt.rs

// Note to self: Remember that traits can store and reference
// a lot of type info related to the types that implemented it.
fn main() {
    println!("{:?}", vec![2,4,5,6,8].map(|&n| n * 2));
    println!("{:?}", vec![1,2,3,4,5].fold(0, |acc, &n| acc + n));
    println!("{:?}", vec!["a", "b", "c"].fold_map(|c| c.to_uppercase()));
}

// Basically, for every container C<T> that implements this trait
// we save the information of his current type T, the type N to be
// mapped to, and a NC collection resulting from mapping C<T> to C<N>.
// And we can call this info by just referencing the trait for the 
// type that implemented it. Type system power that is almost magic!
trait HKT<N> {
    type T;
    type NC;
}

// With native HKT support, Rust would implement something like this
// trait for every type constructor like Vec<_>, so we wouldn't have to
// do something like this manually.
impl<N, T> HKT<N> for Vec<T> {
    type T = T;
    type NC = Vec<N>;
}

trait Monoid {
    fn append(&self, other: &Self) -> Self;
    fn mempty() -> Self;
}

impl Monoid for String {
    fn append(&self, other: &String) -> String {
        let mut new_str = self.clone();
        new_str.push_str(other);
        new_str
    }
    
    fn mempty() -> String {
        String::new()
    }
}
    
trait Functor<N>: HKT<N> {
    fn map<F>(&self, f: F) -> Self::NC where F: Fn(&Self::T) -> N;
}

impl<N, T> Functor<N> for Vec<T> {
    fn map<F>(&self, f: F) -> Vec<N> where F: Fn(&T) -> N {
        let mut mapped = Vec::new();
        for e in self {
            mapped.push(f(e));
        }
        mapped
    }
}

trait Foldable<N>: HKT<N> {
    fn fold<F>(&self, acc: N, f: F) -> N where F: Fn(N, &Self::T) -> N;
    fn fold_map<F>(&self, f: F) -> N where F: Fn(&Self::T) -> N, N: Monoid;
}

impl<T, N> Foldable<N> for Vec<T> {
    fn fold<F>(&self, acc: N, f: F) -> N where F: Fn(N, &T) -> N {
        let mut acc = acc;
        for e in self {
            acc = f(acc, e);
        }
        acc
    }
    
    fn fold_map<F>(&self, f: F) -> N where F: Fn(&T) -> N, N: Monoid {
        if self.len() > 0 {
            let mut acc = f(&self[0]);
            for e in self[1..].iter() {
                acc = acc.append(&f(e));
            }
            acc
        }
        else {
            N::mempty()
        }
    }
}