rust_fp_pfds/
list.rs

1use crate::stack::Stack;
2use crate::StackError;
3use rust_fp_categories::*;
4use std::rc::Rc;
5
6#[derive(Debug, Clone, PartialEq, Eq)]
7pub enum List<A> {
8    Nil,
9    Cons { head: A, tail: Rc<List<A>> },
10}
11
12impl<A: Clone> From<Vec<A>> for List<A> {
13    fn from(vec: Vec<A>) -> Self {
14        vec.iter()
15            .rev()
16            .fold(List::empty(), |acc, e| acc.cons(e.clone()))
17    }
18}
19
20impl<A: Clone> Into<Vec<A>> for List<A> {
21    fn into(self) -> Vec<A> {
22        self.fold_left(vec![], |mut acc, h| {
23            acc.push(h.clone());
24            acc
25        })
26    }
27}
28
29impl<A: Clone> List<A> {
30    pub fn drop(self, n: u32) -> Self {
31        if n == 0 {
32            self
33        } else {
34            match self {
35                List::Nil => List::Nil,
36                List::Cons { tail: t, .. } => Rc::try_unwrap(t).unwrap_or(List::Nil).drop(n - 1),
37            }
38        }
39    }
40
41    pub fn reverse(&self) -> Self {
42        self.fold_left(List::empty(), |acc, h| acc.cons(h.clone()))
43    }
44}
45
46// --- Monoid
47
48impl<A> Empty for List<A> {
49    fn empty() -> List<A> {
50        List::Nil
51    }
52    fn is_empty(&self) -> bool {
53        match self {
54            &List::Nil => true,
55            _ => false,
56        }
57    }
58}
59
60impl<A> Semigroup for List<A> {
61    fn combine(self, other: Self) -> Self {
62        match self {
63            List::Nil => other,
64            List::Cons { head: h, tail: t } => List::Cons {
65                head: h,
66                tail: Rc::new(Rc::try_unwrap(t).unwrap_or(List::Nil).combine(other)),
67            },
68        }
69    }
70}
71
72impl<A> Monoid for List<A> {}
73
74// --- Functor
75
76impl<A: Clone> Functor for List<A> {
77    type Elm = A;
78    type M<U> = List<U>;
79
80    fn fmap<B, F>(self, f: F) -> List<B>
81    where
82        F: Fn(&A) -> B,
83        List<B>: Stack<B>,
84    {
85        if self.is_empty() {
86            List::Nil
87        } else {
88            self.fold_right(List::<B>::empty(), |v, acc| acc.cons(f(&v)))
89        }
90    }
91}
92
93// --- Applicative
94
95impl<A> Pure for List<A> {
96    type Elm = A;
97    type M<U> = List<U>;
98
99    fn pure(value: A) -> List<A> {
100        List::empty().cons(value)
101    }
102
103    fn unit() -> Self::M<()> {
104        List::empty().cons(())
105    }
106}
107
108impl<A> Apply for List<A> {
109    type Elm = A;
110    type M<U> = List<U>;
111
112    fn ap<B, F>(self, fs: Self::M<F>) -> Self::M<B>
113    where
114        F: Fn(&A) -> B,
115        List<B>: Stack<B>,
116    {
117        if self.is_empty() {
118            List::Nil
119        } else {
120            let mut result: List<B> = List::empty();
121            let mut cur1: &List<A> = &self;
122            let mut cur2: &List<F> = &fs;
123            while let List::Cons { ref head, ref tail } = *cur1 {
124                if let List::Cons {
125                    head: ref hf,
126                    tail: ref tf,
127                } = *cur2
128                {
129                    result = result.cons((*hf)(head));
130                    cur1 = tail;
131                    cur2 = tf;
132                }
133            }
134            result
135        }
136    }
137}
138
139impl<A> Applicative for List<A> {}
140
141// --- Bind
142
143impl<A: Clone> Bind for List<A> {
144    type Elm = A;
145    type M<U> = List<U>;
146
147    fn bind<B, F>(self, f: F) -> List<B>
148    where
149        F: Fn(&A) -> List<B>,
150    {
151        if self.is_empty() {
152            List::Nil
153        } else {
154            self.fold_left(List::<B>::empty(), |acc, v| acc.combine(f(&v)))
155        }
156    }
157}
158
159impl<A: Clone> Monad for List<A> {}
160
161// --- Foldable
162
163impl<A: Clone> Foldable for List<A> {
164    type Elm = A;
165
166    fn fold_left<B, F>(&self, b: B, f: F) -> B
167    where
168        F: Fn(B, &Self::Elm) -> B,
169    {
170        match self {
171            &List::Nil => b,
172            &List::Cons { ref head, ref tail } => tail.fold_left(f(b, head), f),
173        }
174    }
175
176    fn fold_right<B, F>(&self, b: B, f: F) -> B
177    where
178        F: Fn(&Self::Elm, B) -> B,
179    {
180        self.reverse().fold_left(b, |b, a| f(a, b))
181    }
182}
183
184impl<A> Stack<A> for List<A> {
185    fn cons(self, value: A) -> Self {
186        List::Cons {
187            head: value,
188            tail: Rc::new(self),
189        }
190    }
191
192    fn head(&self) -> Result<&A, StackError> {
193        match self {
194            &List::Nil => Err(StackError::NoSuchElementError),
195            &List::Cons {
196                head: ref value, ..
197            } => Ok(value),
198        }
199    }
200
201    fn tail(&self) -> Rc<Self> {
202        match self {
203            List::Nil => Rc::new(List::Nil),
204            List::Cons { tail, .. } => Rc::clone(tail),
205        }
206    }
207
208    fn size(&self) -> usize {
209        match self {
210            &List::Nil => 0,
211            &List::Cons { ref tail, .. } => 1 + tail.size(),
212        }
213    }
214
215    fn update(self, index: u32, new_value: A) -> Result<Self, StackError>
216    where
217        Self: Sized,
218    {
219        match self {
220            List::Nil => Err(StackError::IndexOutOfRangeError),
221            List::Cons {
222                head: value,
223                tail: tail_arc,
224            } => match index {
225                0 => {
226                    let t: List<A> =
227                        Rc::try_unwrap(tail_arc).map_err(|_| StackError::RcUnwrapError)?;
228                    Ok(t.cons(new_value))
229                }
230                _ => {
231                    let t: List<A> =
232                        Rc::try_unwrap(tail_arc).map_err(|_| StackError::RcUnwrapError)?;
233                    let updated_tail: List<A> = t.update(index - 1, new_value)?;
234                    Ok(updated_tail.cons(value))
235                }
236            },
237        }
238    }
239
240    fn get(&self, index: u32) -> Result<&A, StackError> {
241        match self {
242            &List::Nil => Err(StackError::NoSuchElementError),
243            &List::Cons {
244                head: ref value,
245                tail: ref tail_arc,
246            } => match index {
247                0 => Ok(value),
248                _ => tail_arc.get(index - 1),
249            },
250        }
251    }
252}
253
254#[cfg(test)]
255mod tests {
256    use crate::list::List;
257    use crate::stack::StackError;
258    use crate::Stack;
259    use rust_fp_categories::Bind;
260    use rust_fp_categories::Empty;
261    use rust_fp_categories::Functor;
262    use rust_fp_categories::Semigroup;
263
264    #[test]
265    fn test_from_vec_to_vec() -> Result<(), StackError> {
266        let v1 = vec![1, 2, 3];
267        let expected1 = v1.clone();
268        let l1 = List::from(v1);
269        let v2: Vec<i32> = l1.into();
270        assert_eq!(v2, expected1);
271        Ok(())
272    }
273
274    #[test]
275    fn test_empty_cons() -> Result<(), StackError> {
276        let list1 = List::empty().cons(1);
277        assert_eq!(*list1.head()?, 1);
278        assert_eq!(*list1.tail(), List::empty());
279        Ok(())
280    }
281
282    #[test]
283    fn test_is_empty() -> Result<(), StackError> {
284        let list1 = List::empty().cons(1);
285        assert_eq!(list1.is_empty(), false);
286        assert_eq!(List::<i32>::empty().is_empty(), true);
287        Ok(())
288    }
289
290    #[test]
291    fn test_combine() -> Result<(), StackError> {
292        let list1 = List::empty().cons(1);
293        let list2 = List::empty().cons(1);
294        let list3 = list1.combine(list2);
295        let vec1: Vec<i32> = list3.into();
296        assert_eq!(vec1, vec![1, 1]);
297        Ok(())
298    }
299
300    #[test]
301    fn test_fmap() -> Result<(), StackError> {
302        let list1: List<i32> = List::from(vec![1, 2, 3, 4, 5]);
303        let list2: List<i32> = list1.fmap(|v| v * 2);
304        let vec1: Vec<i32> = list2.into();
305        assert_eq!(vec1, vec![2, 4, 6, 8, 10]);
306        Ok(())
307    }
308
309    #[test]
310    fn test_bind() -> Result<(), StackError> {
311        let list1: List<i32> = List::from(vec![1, 2, 3, 4, 5]);
312        let list2 = list1.clone();
313        let list3 = list1.bind(|_| List::<i32>::empty());
314        let vec1: Vec<i32> = list3.into();
315        assert_eq!(vec1, Vec::<i32>::empty());
316        let list4 = list2.bind(|v| List::<i32>::empty().cons(*v * 2));
317        let vec2: Vec<i32> = list4.into();
318        assert_eq!(vec2, vec![2, 4, 6, 8, 10]);
319        Ok(())
320    }
321
322    #[test]
323    fn test_head_tail() -> Result<(), StackError> {
324        let list1: List<i32> = List::from(vec![1, 2, 3, 4, 5]);
325        let head = list1.head()?;
326        let tail = list1.tail();
327        assert_eq!(*head, 1);
328        assert_eq!(*tail.as_ref(), List::from(vec![2, 3, 4, 5]));
329        let vec1: Vec<i32> = tail.as_ref().clone().into();
330        assert_eq!(vec1, vec![2, 3, 4, 5]);
331        Ok(())
332    }
333
334    #[test]
335    fn test_get() -> Result<(), StackError> {
336        let list1: List<i32> = List::empty().cons(5).cons(4).cons(3).cons(2).cons(1);
337        let chr = list1.get((list1.size() - 1) as u32)?;
338        assert_eq!(*chr, 5);
339        Ok(())
340    }
341
342    #[test]
343    fn test_eq() -> Result<(), StackError> {
344        let list1: List<i32> = List::from(vec![1, 2, 3, 4, 5]);
345        let list2: List<i32> = List::from(vec![2, 2, 3, 4, 5]);
346        assert_ne!(list1, list2);
347        assert_ne!(*list1.head()?, *list2.head()?);
348        assert_eq!(list1.tail(), list2.tail());
349        Ok(())
350    }
351}
rust_fp_pfds/list.rs

rust_fp_pfds/
list.rs
