iter_utils/
delay.rs

1//! Lazy iterator creation for recursive or deferred iteration patterns.
2
3/// Wraps an iterator of type I by creating it on the first call to `next()`.
4enum DelayState<I: Iterator, F: FnOnce() -> I> {
5    New(Option<F>),
6    Old(I),
7}
8
9pub struct Delayed<I: Iterator, F: FnOnce() -> I>(DelayState<I, F>);
10
11impl<I: Iterator, F: FnOnce() -> I> Iterator for Delayed<I, F> {
12    type Item = I::Item;
13
14    fn next(&mut self) -> Option<Self::Item> {
15        match &mut self.0 {
16            DelayState::New(new) => {
17                let new = new
18                    .take()
19                    .expect("Delay to have either a function or an iterator");
20                let mut old = new();
21                let next = old.next();
22                self.0 = DelayState::Old(old);
23                next
24            }
25            DelayState::Old(old) => old.next(),
26        }
27    }
28}
29
30/// Wraps an iterator created by `new` on the first call to
31/// [`next()`][Iterator::next()].
32///
33/// For example, consider Haskell's [canonical zipWith implementation][hs]:
34/// ```hs
35/// fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
36/// ```
37///
38/// A naive translation to Rust would cause infinite recursion. We can emulate
39/// Haskell's lazy evaluation by delaying the recursive calls:
40/// ```
41/// use iter_utils::delay;
42///
43/// /// Returns an inefficient iterator over the Fibonacci numbers.
44/// fn fibs() -> Box<dyn Iterator<Item = u32>> {
45///     Box::new(
46///         [0, 1]
47///             .into_iter()
48///             .chain(delay(fibs).zip(delay(fibs).skip(1)).map(|(x, y)| x + y)),
49///     )
50/// }
51///
52/// for (got, want) in fibs().zip([0, 1, 1, 2, 3, 5, 8, 13]) {
53///     assert_eq!(got, want);
54/// }
55/// ```
56///
57/// [hs]: https://wiki.haskell.org/The_Fibonacci_sequence#Canonical_zipWith_implementation
58pub fn delay<I: Iterator, F: FnOnce() -> I>(new: F) -> Delayed<I, F> {
59    Delayed(DelayState::New(Some(new)))
60}
61
62/// Lets you call `fibs.delay()` instead of `delay(fibs)`, if such is your wont.
63pub trait Delay<I: Iterator, F: FnOnce() -> I> {
64    fn delay(self) -> Delayed<I, F>;
65}
66
67impl<I: Iterator, F: FnOnce() -> I> Delay<I, F> for F {
68    fn delay(self) -> Delayed<I, F> {
69        delay(self)
70    }
71}
iter_utils/delay.rs

iter_utils/
delay.rs
