trait_theories_std/
fused_iterators.rs

1//! Theory of fused iterators.
2
3/// For all `f: `[`FnMut`], [`Iterator::next`] and [`Iterator::map`]`(·, f)` commutes.
4///
5/// # Proof
6///
7/// [`Iterator::next`] is a [natural transformation] from the [`Iterator`] to [`Option`].
8/// ∎
9///
10/// [natural transformation]: <https://en.wikipedia.org/wiki/Natural_transformation>
11pub fn next_map_commutes<I, F>(mut gen: impl FnMut() -> (I, F))
12where
13    I: Iterator, I::Item: PartialEq,
14    F: FnMut(I::Item) -> I::Item,
15{
16    let a = Vec::from_iter({ let (mut i, f) = gen(); i.next().map(f) });
17    let b = Vec::from_iter({ let (    i, f) = gen(); i.map(f).next() });
18    assert!(a == b);
19}
20
21/// [`Iterator::filter`] then [`Iterator::next`] is equivalent to [`Iterator::find`].
22pub fn filter_next_is_find<I, P>(mut gen: impl FnMut() -> (I, P))
23where
24    I: Iterator, I::Item: PartialEq,
25    P: for<'a> FnMut(&'a I::Item) -> bool,
26{
27    let a = Vec::from_iter({ let (    i, p) = gen(); i.filter(p).next() });
28    let b = Vec::from_iter({ let (mut i, p) = gen(); i.find(p) });
29    assert!(a == b);
30}
31
32/// [`Iterator::filter_map`] with [`bool::then`] can be decomposed into [`Iterator::filter`] and [`Iterator::map`].
33pub fn filter_map_then_decomposable<I, P, F>(mut gen: impl FnMut() -> (I, P, F))
34where
35    I: Iterator, I::Item: PartialEq,
36    P: for<'a> FnMut(&'a I::Item) -> bool,
37    F: FnMut(I::Item) -> I::Item,
38{
39    let a = Vec::from_iter({ let (i, mut p, mut f) = gen(); i.filter_map(move |x| p(&x).then(|| f(x))) });
40    let b = Vec::from_iter({ let (i,     p,     f) = gen(); i.filter(p).map(f) });
41    assert!(a == b);
42}
43
44pub fn check_fused_iterator<I, P, F>(mut gen: impl FnMut() -> (I, P, F))
45where
46    I: Iterator, I::Item: PartialEq,
47    P: for<'a> FnMut(&'a I::Item) -> bool,
48    F: FnMut(I::Item) -> I::Item,
49{
50    next_map_commutes(|| {            let (i, _, f) = gen(); (i, f)    });
51    filter_next_is_find(|| {          let (i, p, _) = gen(); (i, p)    });
52    filter_map_then_decomposable(|| { let (i, p, f) = gen(); (i, p, f) });
53}
54
55#[cfg(test)]
56mod tests {
57    use crate::randutil::MT19937LCG64;
58    use super::check_fused_iterator;
59
60    #[test]
61    fn test_range_iterator() {
62        check_fused_iterator(|| {
63            let mut p_state = MT19937LCG64::new(0x87654321);
64            let p = move |&x: &u32| (x ^ p_state.next()) % 2 == 0;
65
66            let mut f_state = MT19937LCG64::new(0x86407531);
67            let f = move |x: u32| x ^ f_state.next();
68
69            (0u32..64u32, p, f)
70        });
71    }
72}
trait_theories_std/fused_iterators.rs

trait_theories_std/
fused_iterators.rs
