trait-theories-std 0.1.0

//! Theory of fused iterators.

/// For all `f: `[`FnMut`], [`Iterator::next`] and [`Iterator::map`]`(·, f)` commutes.
///
/// # Proof
///
/// [`Iterator::next`] is a [natural transformation] from the [`Iterator`] to [`Option`].
/// ∎
///
/// [natural transformation]: <https://en.wikipedia.org/wiki/Natural_transformation>
pub fn next_map_commutes<I, F>(mut gen: impl FnMut() -> (I, F))
where
    I: Iterator, I::Item: PartialEq,
    F: FnMut(I::Item) -> I::Item,
{
    let a = Vec::from_iter({ let (mut i, f) = gen(); i.next().map(f) });
    let b = Vec::from_iter({ let (    i, f) = gen(); i.map(f).next() });
    assert!(a == b);
}

/// [`Iterator::filter`] then [`Iterator::next`] is equivalent to [`Iterator::find`].
pub fn filter_next_is_find<I, P>(mut gen: impl FnMut() -> (I, P))
where
    I: Iterator, I::Item: PartialEq,
    P: for<'a> FnMut(&'a I::Item) -> bool,
{
    let a = Vec::from_iter({ let (    i, p) = gen(); i.filter(p).next() });
    let b = Vec::from_iter({ let (mut i, p) = gen(); i.find(p) });
    assert!(a == b);
}

/// [`Iterator::filter_map`] with [`bool::then`] can be decomposed into [`Iterator::filter`] and [`Iterator::map`].
pub fn filter_map_then_decomposable<I, P, F>(mut gen: impl FnMut() -> (I, P, F))
where
    I: Iterator, I::Item: PartialEq,
    P: for<'a> FnMut(&'a I::Item) -> bool,
    F: FnMut(I::Item) -> I::Item,
{
    let a = Vec::from_iter({ let (i, mut p, mut f) = gen(); i.filter_map(move |x| p(&x).then(|| f(x))) });
    let b = Vec::from_iter({ let (i,     p,     f) = gen(); i.filter(p).map(f) });
    assert!(a == b);
}

pub fn check_fused_iterator<I, P, F>(mut gen: impl FnMut() -> (I, P, F))
where
    I: Iterator, I::Item: PartialEq,
    P: for<'a> FnMut(&'a I::Item) -> bool,
    F: FnMut(I::Item) -> I::Item,
{
    next_map_commutes(|| {            let (i, _, f) = gen(); (i, f)    });
    filter_next_is_find(|| {          let (i, p, _) = gen(); (i, p)    });
    filter_map_then_decomposable(|| { let (i, p, f) = gen(); (i, p, f) });
}

#[cfg(test)]
mod tests {
    use crate::randutil::MT19937LCG64;
    use super::check_fused_iterator;

    #[test]
    fn test_range_iterator() {
        check_fused_iterator(|| {
            let mut p_state = MT19937LCG64::new(0x87654321);
            let p = move |&x: &u32| (x ^ p_state.next()) % 2 == 0;

            let mut f_state = MT19937LCG64::new(0x86407531);
            let f = move |x: u32| x ^ f_state.next();

            (0u32..64u32, p, f)
        });
    }
}