use crate::stack::Stack;
use crate::StackError;
use rust_fp_categories::*;
use std::rc::Rc;
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum List<A> {
Nil,
Cons { head: A, tail: Rc<List<A>> },
}
impl<A: Clone> From<Vec<A>> for List<A> {
fn from(vec: Vec<A>) -> Self {
vec.iter()
.rev()
.fold(List::empty(), |acc, e| acc.cons(e.clone()))
}
}
impl<A: Clone> Into<Vec<A>> for List<A> {
fn into(self) -> Vec<A> {
self.fold_left(vec![], |mut acc, h| {
acc.push(h.clone());
acc
})
}
}
impl<A: Clone> List<A> {
pub fn drop(self, n: u32) -> Self {
if n == 0 {
self
} else {
match self {
List::Nil => List::Nil,
List::Cons { tail: t, .. } => Rc::try_unwrap(t).unwrap_or(List::Nil).drop(n - 1),
}
}
}
pub fn reverse(&self) -> Self {
self.fold_left(List::empty(), |acc, h| acc.cons(h.clone()))
}
}
impl<A> Empty for List<A> {
fn empty() -> List<A> {
List::Nil
}
fn is_empty(&self) -> bool {
match self {
&List::Nil => true,
_ => false,
}
}
}
impl<A> Semigroup for List<A> {
fn combine(self, other: Self) -> Self {
match self {
List::Nil => other,
List::Cons { head: h, tail: t } => List::Cons {
head: h,
tail: Rc::new(Rc::try_unwrap(t).unwrap_or(List::Nil).combine(other)),
},
}
}
}
impl<A> Monoid for List<A> {}
impl<A: Clone> Functor for List<A> {
type Elm = A;
type M<U> = List<U>;
fn fmap<B, F>(self, f: F) -> List<B>
where
F: Fn(&A) -> B,
List<B>: Stack<B>,
{
if self.is_empty() {
List::Nil
} else {
self.fold_right(List::<B>::empty(), |v, acc| acc.cons(f(&v)))
}
}
}
impl<A> Pure for List<A> {
type Elm = A;
type M<U> = List<U>;
fn pure(value: A) -> List<A> {
List::empty().cons(value)
}
fn unit() -> Self::M<()> {
List::empty().cons(())
}
}
impl<A> Apply for List<A> {
type Elm = A;
type M<U> = List<U>;
fn ap<B, F>(self, fs: Self::M<F>) -> Self::M<B>
where
F: Fn(&A) -> B,
List<B>: Stack<B>,
{
if self.is_empty() {
List::Nil
} else {
let mut result: List<B> = List::empty();
let mut cur1: &List<A> = &self;
let mut cur2: &List<F> = &fs;
while let List::Cons { ref head, ref tail } = *cur1 {
if let List::Cons {
head: ref hf,
tail: ref tf,
} = *cur2
{
result = result.cons((*hf)(head));
cur1 = tail;
cur2 = tf;
}
}
result
}
}
}
impl<A> Applicative for List<A> {}
impl<A: Clone> Bind for List<A> {
type Elm = A;
type M<U> = List<U>;
fn bind<B, F>(self, f: F) -> List<B>
where
F: Fn(&A) -> List<B>,
{
if self.is_empty() {
List::Nil
} else {
self.fold_left(List::<B>::empty(), |acc, v| acc.combine(f(&v)))
}
}
}
impl<A: Clone> Monad for List<A> {}
impl<A: Clone> Foldable for List<A> {
type Elm = A;
fn fold_left<B, F>(&self, b: B, f: F) -> B
where
F: Fn(B, &Self::Elm) -> B,
{
match self {
&List::Nil => b,
&List::Cons { ref head, ref tail } => tail.fold_left(f(b, head), f),
}
}
fn fold_right<B, F>(&self, b: B, f: F) -> B
where
F: Fn(&Self::Elm, B) -> B,
{
self.reverse().fold_left(b, |b, a| f(a, b))
}
}
impl<A> Stack<A> for List<A> {
fn cons(self, value: A) -> Self {
List::Cons {
head: value,
tail: Rc::new(self),
}
}
fn head(&self) -> Result<&A, StackError> {
match self {
&List::Nil => Err(StackError::NoSuchElementError),
&List::Cons {
head: ref value, ..
} => Ok(value),
}
}
fn tail(&self) -> Rc<Self> {
match self {
List::Nil => Rc::new(List::Nil),
List::Cons { tail, .. } => Rc::clone(tail),
}
}
fn size(&self) -> usize {
match self {
&List::Nil => 0,
&List::Cons { ref tail, .. } => 1 + tail.size(),
}
}
fn update(self, index: u32, new_value: A) -> Result<Self, StackError>
where
Self: Sized,
{
match self {
List::Nil => Err(StackError::IndexOutOfRangeError),
List::Cons {
head: value,
tail: tail_arc,
} => match index {
0 => {
let t: List<A> =
Rc::try_unwrap(tail_arc).map_err(|_| StackError::RcUnwrapError)?;
Ok(t.cons(new_value))
}
_ => {
let t: List<A> =
Rc::try_unwrap(tail_arc).map_err(|_| StackError::RcUnwrapError)?;
let updated_tail: List<A> = t.update(index - 1, new_value)?;
Ok(updated_tail.cons(value))
}
},
}
}
fn get(&self, index: u32) -> Result<&A, StackError> {
match self {
&List::Nil => Err(StackError::NoSuchElementError),
&List::Cons {
head: ref value,
tail: ref tail_arc,
} => match index {
0 => Ok(value),
_ => tail_arc.get(index - 1),
},
}
}
}
#[cfg(test)]
mod tests {
use crate::list::List;
use crate::stack::StackError;
use crate::Stack;
use rust_fp_categories::Bind;
use rust_fp_categories::Empty;
use rust_fp_categories::Functor;
use rust_fp_categories::Semigroup;
#[test]
fn test_from_vec_to_vec() -> Result<(), StackError> {
let v1 = vec![1, 2, 3];
let expected1 = v1.clone();
let l1 = List::from(v1);
let v2: Vec<i32> = l1.into();
assert_eq!(v2, expected1);
Ok(())
}
#[test]
fn test_empty_cons() -> Result<(), StackError> {
let list1 = List::empty().cons(1);
assert_eq!(*list1.head()?, 1);
assert_eq!(*list1.tail(), List::empty());
Ok(())
}
#[test]
fn test_is_empty() -> Result<(), StackError> {
let list1 = List::empty().cons(1);
assert_eq!(list1.is_empty(), false);
assert_eq!(List::<i32>::empty().is_empty(), true);
Ok(())
}
#[test]
fn test_combine() -> Result<(), StackError> {
let list1 = List::empty().cons(1);
let list2 = List::empty().cons(1);
let list3 = list1.combine(list2);
let vec1: Vec<i32> = list3.into();
assert_eq!(vec1, vec![1, 1]);
Ok(())
}
#[test]
fn test_fmap() -> Result<(), StackError> {
let list1: List<i32> = List::from(vec![1, 2, 3, 4, 5]);
let list2: List<i32> = list1.fmap(|v| v * 2);
let vec1: Vec<i32> = list2.into();
assert_eq!(vec1, vec![2, 4, 6, 8, 10]);
Ok(())
}
#[test]
fn test_bind() -> Result<(), StackError> {
let list1: List<i32> = List::from(vec![1, 2, 3, 4, 5]);
let list2 = list1.clone();
let list3 = list1.bind(|_| List::<i32>::empty());
let vec1: Vec<i32> = list3.into();
assert_eq!(vec1, Vec::<i32>::empty());
let list4 = list2.bind(|v| List::<i32>::empty().cons(*v * 2));
let vec2: Vec<i32> = list4.into();
assert_eq!(vec2, vec![2, 4, 6, 8, 10]);
Ok(())
}
#[test]
fn test_head_tail() -> Result<(), StackError> {
let list1: List<i32> = List::from(vec![1, 2, 3, 4, 5]);
let head = list1.head()?;
let tail = list1.tail();
assert_eq!(*head, 1);
assert_eq!(*tail.as_ref(), List::from(vec![2, 3, 4, 5]));
let vec1: Vec<i32> = tail.as_ref().clone().into();
assert_eq!(vec1, vec![2, 3, 4, 5]);
Ok(())
}
#[test]
fn test_get() -> Result<(), StackError> {
let list1: List<i32> = List::empty().cons(5).cons(4).cons(3).cons(2).cons(1);
let chr = list1.get((list1.size() - 1) as u32)?;
assert_eq!(*chr, 5);
Ok(())
}
#[test]
fn test_eq() -> Result<(), StackError> {
let list1: List<i32> = List::from(vec![1, 2, 3, 4, 5]);
let list2: List<i32> = List::from(vec![2, 2, 3, 4, 5]);
assert_ne!(list1, list2);
assert_ne!(*list1.head()?, *list2.head()?);
assert_eq!(list1.tail(), list2.tail());
Ok(())
}
}