Shared via Rust Playground

playground.rs

use std::collections::VecDeque;

// The kind * -> *
trait TypeToType<Input> {
    type Output;
}

struct Vec_;
struct VecDeque_;

impl<T> TypeToType<T> for Vec_ {
    type Output = Vec<T>;
}

impl<T> TypeToType<T> for VecDeque_ {
    type Output = VecDeque<T>;
}

// A collection that can be mapped over.
// So e.g. converting Vec<T> to an arbitary Vec<U>
trait Mappable 
    where Self: Sized,
{
    type E;
    type HKT: TypeToType<Self::E, Output=Self>;

    fn map<F, O>(self, f: F) -> <Self::HKT as TypeToType<O>>::Output
        where F: FnMut(Self::E) -> O,
              Self::HKT: TypeToType<O>;
}


// FIXME: these are a hack to convince the compiler to do its damn job.
fn project_vec<O>(v: Vec<O>) -> <Vec_ as TypeToType<O>>::Output { v }
fn project_vec_deque<O>(v: VecDeque<O>) -> <VecDeque_ as TypeToType<O>>::Output { v }


impl<T> Mappable for Vec<T> {
    type E = T;
    type HKT = Vec_;
    
    fn map<F, O>(self, mut f: F) -> <Self::HKT as TypeToType<O>>::Output
        where F: FnMut(Self::E) -> O,
              Self::HKT: TypeToType<O>
    {
        let r: Vec<O> = self.into_iter().map(&mut f).collect();
        project_vec::<O>(r)
    }
        
}


impl<T> Mappable for VecDeque<T> {
    type E = T;
    type HKT = VecDeque_;
    
    fn map<F, O>(self, mut f: F) -> <Self::HKT as TypeToType<O>>::Output
        where F: FnMut(Self::E) -> O,
              Self::HKT: TypeToType<O>
    {
        let r: VecDeque<O> = self.into_iter().map(&mut f).collect();
        project_vec_deque::<O>(r)
    }
        
}

fn main() {
    let vals = vec![1, 2, 3, 4, 5];
    let bools = vals.clone().map(|x| x < 3);
    
    let vals2: VecDeque<_> = vals.into_iter().collect();
    let bools2 = vals2.clone().map(|x| x < 3);
    
    println!("{:?} {:?}", bools, bools2);
}