1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109

/**
(
<em>a</em><sub>0</sub>,
<em>a</em><sub>1</sub>,
<em>a</em><sub>2</sub>,
...
),
&nbsp;&rarr;&nbsp;
&nbsp;&rarr;&nbsp;
((<em>a</em><sub>0</sub>) &#x2297; <em>a</em><sub>1</sub>) &#x2297; <em>a</em><sub>2</sub>) &#x2297; ...

*/
pub trait FoldlIterator<E>: Iterator<Item=E> + Sized {
    /**
Folds the elements of the iterator together, from left to right, using `f`.

Returns `None` if the iterator is empty.
    */
    fn foldl<F: FnMut(E, E) -> E>(mut self, f: F) -> Option<E> {
        let first = match self.next() {
            None => return None,
            Some(e) => e
        };

        Some(self.fold(first, f))
    }

    /**
Folds the elements of the iterator together, from left to right, using `f.

In addition, the first element is transformed using `map` before folding begins.

Returns `None` if the iterator is empty.
    */
    fn foldl_map<E1, F: FnMut(E1, E) -> E1, MapFn: FnOnce(E) -> E1>(mut self, map: MapFn, f: F) -> Option<E1> {
        let first = match self.next() {
            None => return None,
            Some(e) => map(e)
        };

        Some(self.fold(first, f))
    }
}

impl<It, E> FoldlIterator<E> for It where It: Iterator<Item=E> {}

#[test]
fn test_foldl() {
    use std::borrow::ToOwned;

    let vs = vec!["a", "b", "c"];
    let vs = vs.into_iter().map(|e| e.to_owned());
    assert_eq!(Some("((a, b), c)".to_owned()), vs.foldl(|a,b| format!("({}, {})", a, b)));
}

#[test]
fn test_foldl_map() {
    use std::borrow::ToOwned;

    let v = vec!["a", "b", "c"];
    let r = v.into_iter().foldl_map(|e| e.to_owned(), |e,f| (e+", ")+f);
    assert_eq!(r, Some("a, b, c".to_owned()));
}

/**
(
...,
<em>a</em><sub><em>n</em>-2</sub>,
<em>a</em><sub><em>n</em>-1</sub>,
<em>a</em><sub><em>n</em></sub>,
),
&#x2297;
&rarr;
... &#x2297; (<em>a</em><sub><em>n</em>-2</sub> &#x2297; (<em>a</em><sub><em>n</em>-1</sub> &#x2297; (<em>a</em><sub><em>n</em></sub>)))

*/
pub trait FoldrIterator<E>: DoubleEndedIterator + Iterator<Item=E> + Sized {
    /**
Folds the elements of the iterator together, from right to left, using `f`.

Returns `None` if the iterator is empty.
    */
    fn foldr<F: FnMut(E, E) -> E>(mut self, mut f: F) -> Option<E> {
        let mut last = match self.next_back() {
            None => return None,
            Some(e) => e
        };

        loop {
            match self.next_back() {
                None => break,
                Some(e) => last = f(e, last)
            }
        }

        Some(last)
    }
}

impl<It, E> FoldrIterator<E> for It where It: DoubleEndedIterator + Iterator<Item=E> {}

#[test]
fn test_foldr() {
    use std::borrow::ToOwned;

    let vs = vec!["a", "b", "c"];
    let vs = vs.into_iter().map(|e| e.to_owned());
    assert_eq!(Some("(a, (b, c))".to_owned()), vs.foldr(|a,b| format!("({}, {})", a, b)));
}