Playground: Rust Playground
I'm trying to chain iterators in a recursive function. The function is supposed to return a iterator, but using .chain results in a Chain. A Chain is iterator-like - it offers .map - but it won't convert to an iterator. How do I do this?
Your two branches have incompatible types, impl Trait must resolve to a single type. In this case, you can use Box<dyn Iterator<Item = u32>> instead for example:
fn subdivide(val: u32) -> Box<dyn Iterator<Item = u32>> {
if val == 0 {
Box::new(vec![].into_iter())
} else {
Box::new(vec![val].into_iter()
.chain(subdivide(val-1)))
}
}
It's likely not possible to achieve this in a purely static way. The issue isn't that the function is recursive, but that the return type is recursive.
Using -> impl Trait is akin to asking the compiler to infer a concrete return type on its own. If you can't envision such a concrete type, the compiler can't either. In the if-else block, the true branch returns a IntoIter<u32> type, while the false branch returns a Chain<IntoIter<u32>, <return type of the same function>>. Even if we refactor the true branch to return a Chain<A, B> somehow, specifying its generic parameters would be impossible due to their recursive nature.
Shot:
fn subdivide(val: u32) -> impl Iterator<Item = u32> {
(1..=val).rev()
}
fn main() {
println!("Sequence: {:?}", subdivide(10).collect::<Vec<u32>>())
}
Obviously, this was a toy example; I don't expect this suggestion to solve your real problem, but it does solve your toy one, quite tidily, even for very large val arguments.
Chaser:
fn subdivide(val: u32) -> impl Iterator<Item = u32> {
SubdividedIter::from(val)
}
enum SubdividedIter {
Done,
Remaining(u32),
}
impl From<u32> for SubdividedIter {
fn from(val: u32) -> Self {
match val {
0 => Self::Done,
n => Self::Remaining(n),
}
}
}
impl Iterator for SubdividedIter {
type Item = u32;
fn next(&mut self) -> Option<Self::Item> {
let (value, state) = match self {
Self::Done => (None, Self::Done),
Self::Remaining(n) => (Some(*n), n.saturating_sub(1).into())
};
*self = state;
value
}
}
fn main() {
println!("Sequence: {:?}", subdivide(10).collect::<Vec<u32>>())
}
Since subdivided must return a single iterator type, and since there is no type that includes both std::vec::IntoIter and std::iter::Chain, we can (and must) write our own. Most of the logic for recursively solving the problem moves into the iterator, becoming a state machine in the process. In this case, the state machine is relatively simple, but I'm sure your real problem requires more nuance.
It's not really possible to use iter::Chain here, since it exposes the underlying iterators through its type parameters. The number of layers of such iterators in your approach is dependent on val, and Rust doesn't allow that kind of value-dependent typing.
Edit: @firebits.io's approach is also great - though it does require generating what amounts to a singly-linked list of val elements when it's called, before iteration can begin.
OK, then I probably should go back to just returning a Vec and concatenating the Vec items. I was trying to reduce the number of allocations, but if Box and dyn become involved, that's probably a lose.
If you can change the recursion into a loop, then this should work.
How about passing along a &mut Vec and pushing to it directly, like so?
Thanks. The actual code, non-iterator, is below. Not runnable without a lot more code.
This is part of the tiling algorithm for a slippy map. It's for distant impostors in a 3D world. There's a hierarchy of map tiles (they're 3D objects here), and if you're close to the camera, smaller tiles with more detail have to be used. It's like Google Earth.
I was kind of hoping to get an iterator out, because the next step is a filter which checks which ones we already are drawing and computes the changes. But the actual number of tiles that comes out of this process is around 50, even for a world thousands of tiles across, because most are not subdivided. So overhead is not large. Using an iterator would just be a style thing.
/// Calculate relevant tiles.
/// Recursively subdivides the tiles, discarding any exclude regions.
///
/// If there's no overlap with the exclude regions, return this tile.
/// Otherwise subdivide into quadrants and try again.
fn calculate_impostorable_tiles(base_tile_size: [u32;2], tile: RegionBox, exclude_regions: &[RegionBox]) -> Vec<RegionBox> {
println!("Impostorable tile: {:?}", tile); // ***TEMP***
// Sanity check on input
check_valid_tile(base_tile_size, &tile);
// Does this tile overlap any regions we can't impostor?
if exclude_regions.iter().find(|&item| item.overlap(tile)).is_none() {
return vec![tile]
}
// Check if further subdivision possible.
if tile.size[0] <= base_tile_size[0] || tile.size[1] <= base_tile_size[1] {
return vec![]; // done
}
// Yes, there is overlap. Divide tile into four quadrants and recurse.
let halfsizex = tile.size[0] / 2;
let halfsizey = tile.size[1] / 2;
let halfsize = [halfsizex, halfsizey];
//////let halflod = tile.1 - 1;
let pos = tile.region_handle.to_region_loc_u32();
// Create a quadrant
let subtile = |offset: [u32;2]| RegionBox {
region_handle: RegionHandle::from_region_loc([pos[0] + halfsizex * offset[0], pos[1] + halfsizey * offset[1]]),
size: halfsize
};
// Concatenate results from the four quadrants
let mut subtiles = calculate_impostorable_tiles(base_tile_size, subtile([0,0]), exclude_regions);
subtiles.extend(calculate_impostorable_tiles(base_tile_size, subtile([1,0]), exclude_regions));
subtiles.extend(calculate_impostorable_tiles(base_tile_size, subtile([0,1]), exclude_regions));
subtiles.extend(calculate_impostorable_tiles(base_tile_size, subtile([1,1]), exclude_regions));
subtiles
}
The part at the end is the recursion. I'd tried doing that with Chain, but, as others pointed out, that won't work easily, if at all.
That makes sense to me.
You could definitely write your own iterator as @derspiny showed. But it would be more complex since your algorithm would have to be changed into a state machine. That's a lot of trouble when an iterator isn't really necessary. And I don't think the result would be as readable as a recursive algorithm that adds to a Vec.