List abstracted over Rc/Arc

list.rs

// https://play.rust-lang.org/?gist=6f69dfefc6dd93d941cabb9a1634dcee
use std::fmt;
use std::iter::FromIterator;
use std::rc::Rc;
use std::sync::Arc;
use std::ops::Deref;

// pub trait HKT<U> where U: ?Sized {
//     type C; // Current type
//     type T; // Type with C swapped with U
// }

// macro_rules! derive_hkt {
//     ($t:ident) => {
//         impl<T, U> HKT<U> for $t<T> {
//             type C = T;
//             type T = $t<U>;
//         }
//     }
// }

// derive_hkt!(Rc);
// derive_hkt!(Arc);


pub trait Ref: Clone + Deref {
    fn new(value: Self::Target) -> Self;
}

impl<T> Ref for Rc<T> {
    fn new(value: T) -> Self {
        Rc::new(value)
    }
}

impl<T> Ref for Arc<T> {
    fn new(value: T) -> Self {
        Arc::new(value)
    }
}

pub trait RefCtr<T>: Sized {
    type ValRef: Ref<Target = T>;
    type ListRef: Ref<Target = ListInner<Self, T>>;
    type L: Ref<Target = List<Self, T>>;
}

pub enum RcCtr {}

impl<T> RefCtr<T> for RcCtr {
    type ValRef = Rc<T>;
    type ListRef = Rc<ListInner<Self, T>>;
    type L = Rc<List<Self, T>>;
}



pub enum ArcCtr {}

impl<T> RefCtr<T> for ArcCtr {
    type ValRef = Arc<T>;
    type ListRef = Arc<ListInner<Self, T>>;
    type L = Arc<List<Self, T>>;
}


pub enum ListInner<R, V> 
where
    R: RefCtr<V>,
{
    Nil,
    Cons { value: R::ValRef, rest: List<R, V> },
}

pub struct List<R, V> 
where
    R: RefCtr<V>,
{
    inner: R::ListRef,
}

impl<R, V> Clone for List<R, V>
where
    R: RefCtr<V>,
{
    fn clone(&self) -> Self {
        List {
            inner: self.inner.clone(),
        }
    }
}


impl<R, V> List<R, V> 
where
    R: RefCtr<V>,
{
    fn new() -> Self {
        List {
            inner: R::ListRef::new(ListInner::Nil),
        }
    }

    fn cons(&self, value: V) -> Self {
        List {
            inner: R::ListRef::new(ListInner::Cons {
                value: R::ValRef::new(value),
                rest: self.clone(),
            }),
        }
    }
    
    fn view(&self) -> Option<(R::ValRef, Self)> {
        match *self.inner {
            ListInner::Nil => None,
            ListInner::Cons { ref value, ref rest } => {
                Some((value.clone(), rest.clone()))
            }
        }
    }
    
    fn iter(&self) -> ListIter<R, V> {
        ListIter { rest: self.clone() }
    }
}

impl<R, V> fmt::Debug for List<R, V> 
where
    R: RefCtr<V>,
    R::ValRef: fmt::Debug,
{
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        f.debug_list().entries(self.iter()).finish()
    }
}

impl<R, V> FromIterator<V> for List<R, V> 
where
    R: RefCtr<V>,
{
    fn from_iter<I: IntoIterator<Item = V>>(iter: I) -> Self {
        iter.into_iter().fold(List::new(), |vs, v| vs.cons(v))
    }
}

pub struct ListIter<R, V> 
where
    R: RefCtr<V>,
{
    rest: List<R, V>,
}

impl<R, V> Iterator for ListIter<R, V> 
where
    R: RefCtr<V>,
{
    type Item = R::ValRef;
    
    fn next(&mut self) -> Option<Self::Item> {
        let (value, rest) = self.rest.view()?;
        self.rest = rest;
        Some(value)
    }
}

impl<R, V> IntoIterator for List<R, V> 
where
    R: RefCtr<V>,
{
    type Item = R::ValRef;
    type IntoIter = ListIter<R, V>;
    
    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

pub type RcList<T> = List<RcCtr, T>;
pub type ArcList<T> = List<ArcCtr, T>;

trait TestSend: Send {}
impl<T: Send + Sync> TestSend for ArcList<T> {}

fn main() {
    let vs_arc: List<ArcCtr, _> = (1..32).collect();
    println!("{:?}", vs_arc);

    let vs_rc: List<RcCtr, _> = (1..32).collect();
    println!("{:?}", vs_rc);
}