Generative iterator that gives out references to itself

Question

For Advent of Code Day 17 (problem statement isn't super important), what I want to do is have a type:

#[derive(Debug, Clone)]
struct Cubes {
    active: HashSet<Vec<i32>>,
}

And create an Iterator that yields out successive instances of that type. I can (did) implement this:

impl Iterator for Cubes {
    type Item = Cubes;
    fn next(&mut self) -> Option<Cubes> { ... }
}

Which works fine, but is pretty expensive since what I end up doing is both modifying the Cubes locally and also returning a copy of it.

What I'd like do is have the Iterator mutate its internal state and hand out a reference to it, so that I don't need to make any copies.

Even in the most trivial case of like an infinite iterator that just hands out a reference, I can't come up with a formulation of this that checks:

// this doesn't actually compile
fn iter(cc: &mut Cubes) -> impl Iterator<Item=&Cubes> {
    std::iter::from_fn(move ||{
        Some(&*cc)
    })
}

whereas what I'm doing is roughly equivalent to this (which does compile, but I am trying to improve):

fn iter(cc: ConwayCubes) -> impl Iterator<Item=ConwayCubes> {
    std::iter::from_fn(move ||{
        Some(cc.clone())
    })
}

I suppose I could also restructure the problem to hand out something like Rc<Cubes>, which would still do copies but those copies would be cheap, but I'm curious if there's a way to do this with references.

So the first `next()` you return a reference to an instance of `Cubes`. Now the second `next()` you want to modify that same instance and return the same reference again? Thus any subsequent `next()` call will invalidate all the previous? If what I said is what you mean, then that is why you cannot do that. — vallentin, Dec 17 '20 at 19:59
Why not [just do this](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=ea5ac72d2de0d1f8ee35b8d7d9f216b8)? Also like @vallentin said you can't mutate something if you have loaned out immutable references to it. — pretzelhammer, Dec 17 '20 at 20:05
@vallentin Yeah, phrasing it that way seems impossible. But is there any way to do this sort of thing efficiently? — Barry, Dec 17 '20 at 20:07
@pretzelhammer I actually do need mutation. I'm trying to do the sequence `x`, `f(x)`, `f(f(x))`, `f(f(f(x)))`... just without the copying. — Barry, Dec 17 '20 at 20:08
@Barry the issue is that, supposed you did `collect()` and now have a `Vec<&Cubes>` with `4` items, then that `Vec` would _contain_ `f(f(f(x)))`, `f(f(f(x)))`, `f(f(f(x)))`, `f(f(f(x)))` and not `x`, `f(x)`, `f(f(x))`, `f(f(f(x)))` — vallentin, Dec 17 '20 at 20:09
It sounds more like you'd want `fn next_state(&mut self)`, then in the event you actually want to create an `Iterator` of all states over time, you could `impl IntoIterator` where you then do use `clone()` — vallentin, Dec 17 '20 at 20:13
@vallentin Can you throw that into an answer? This sounds very helpful. — Barry, Dec 17 '20 at 20:17

vallentin · Accepted Answer · 2020-12-17T20:49:54.373

As mentioned in the comments, the issue is that you cannot return a reference to something while subsequently wanting to mutate it. Because that something is still being "borrowed" and referenced elsewhere.

If that was possible, then suppose you collect()ed everything into a Vec<&Cubes>, then if that resulted in a Vec<&Cubes> with 3 items. Then given that it's 3 references to the same instance, then all 3 items would have the same state as the last item.

In short you'd not end up with x, f(x), f(f(x)) as you want, but instead f(f(x)), f(f(x)), f(f(x))

Since you want less cloning, then it sounds more like you just want an fn next_state(&mut self) method. Then you could iterate and call cubes.next_state() which would update cubes to its next state, while no needless cloning would occur.

impl Cubes {
    fn next_state(&mut self) {
        ...
    }
}

fn main() {
    for _ in 0..10 {
        // do something with cubes

        cubes.next_state();
    }
}

Along the lines of what you already did, you could then create an iter_states() method using iter::from_fn(), which calls next_state() and returns a clone.

impl Cubes {
    fn iter_states(&self) -> impl Iterator<Item = Cubes> {
        let mut next = self.clone();
        iter::from_fn(move || {
            let current = next.clone();
            next.next_state();
            Some(current)
        })
    }
}

Alternatively, you could also introduce a custom CubesIter Iterator type. Then you can impl IntoIterator for Cubes which converts Cubes into an Iterator.

struct CubesIter {
    next: Cubes,
}

impl Iterator for CubesIter {
    type Item = Cubes;

    fn next(&mut self) -> Option<Self::Item> {
        let current = self.next.clone();
        self.next.next_state();
        Some(current)
    }
}

impl IntoIterator for Cubes {
    type Item = Cubes;
    type IntoIter = CubesIter;

    fn into_iter(self) -> Self::IntoIter {
        CubesIter { next: self }
    }
}

This would then allow you to do:

let cubes: Cubes = ...;

for state in cubes {
    ...
}

Note that the above will iterate indefinitely. So you'd have to add some stop state or condition.

Generative iterator that gives out references to itself

1 Answers1