Type problem trying to create an iterator wrapper

I'm trying to create an iterator that folds blocks of input, delimited by possibly multiple consecutive instances of some delimiter.

Let's say we have the following:

  let v = [0,0,1,2,3,0,0,0,4,5,6,0];

and we want to apply a folding (aggregating) function, like sum, to the blocks obtained by using 0 (or any number of consecutive 0s as delimiter), then we can wrap the iterator obtained by v.into_iter() in a BlockFolder struct (see code below) that also takes as argument a closure that should return true if the current item is a delimiter and another closure that takes an accumulator and the current item and returns the folded value up to that point.

So, for the example above, the first call to next on the BlockFolder will yield Some(6) (because 1+2+3=6) and the second call Some(15) (because 4+5+6=15).

My code looks like:

pub struct BlockFolder<I, DF, FF> {
    iter: I,
    delim_func: DF,
    fold_func: FF,
}
impl<I, DF, FF> BlockFolder<I, DF, FF>
where
    I: Iterator,
    DF: FnMut(&I::Item) -> bool,
    FF: FnMut(&I::Item, &I::Item) -> I::Item,
{
    pub fn new(iter: I, delim_func: DF, fold_func: FF) -> BlockFolder<I, DF, FF> {
        BlockFolder {
            iter,
            delim_func,
            fold_func,
        }
    }
    // skips until a value is found, then return that value
    fn skip(&mut self) -> Option<I::Item> {
        loop {
            let v = self.iter.next()?;
            let is_delim = (self.delim_func)(&v);
            if !is_delim {
                return Some(v);
            }
        }
    }
    fn fold(&mut self, orig: Option<I::Item>) -> Option<I::Item> {
        let mut accum = orig.unwrap();
        loop {
            match self.iter.next() {
                Some(v) => {
                    if (self.delim_func)(&v) {
                        // We stepped inside the next separator, so we stop
                        return Some(accum);
                    }
                    accum = (self.fold_func)(&accum, &v)
                }
                // The item returned by skip was a singular, last item,
                // so, self.iter.next() above resulted in None.
                None => return Some(accum),
            };
        }
    }
}
impl<I, DF, FF> Iterator for BlockFolder<I, DF, FF>
where
    I: Iterator,
    DF: FnMut(&I::Item) -> bool,
    FF: FnMut(&I::Item, &I::Item) -> I::Item,
{
    type Item = I::Item;

    fn next(&mut self) -> Option<Self::Item> {
        let orig = self.skip()?;
        Some(self.fold(Some(orig))?)
    }
}

My tests look like:

use block_folder::BlockFolder;

#[test]
fn test_owned() {
    let v = [0, 0, 1, 2, 3, 0, 4, 5, 0, 0, 0, 6, 7, 8, 0, 0];
    let mut bc = BlockFolder::new(v.into_iter(), |v| *v == 0, |orig, v| v + orig);
    assert_eq!(bc.next(), Some(6));
    assert_eq!(bc.next(), Some(9));
    assert_eq!(bc.next(), Some(21));
    assert_eq!(bc.next(), None);
}

#[test]
fn test_borrowed() {
    let v = [0, 0, 1, 2, 3, 0, 4, 5, 0, 0, 0, 6, 7, 8, 0, 0];
    let mut bc = BlockFolder::new(v.iter(), |v| **v == 0, |orig, v| **v + **orig);
    assert_eq!(bc.next(), Some(&6));
    assert_eq!(bc.next(), Some(&9));
    assert_eq!(bc.next(), Some(&21));
    assert_eq!(bc.next(), None);
}

The problem I'm having is that whilst test_owned works fine, test_borrowed won't compile, because according to the type system, the fold_func returns an Iterator::Item. In this case, Iterator::Item is a reference type, because of passing in v.iter() instead of v.into_iter() as iterator and I can't simply cast the sum to a reference, because then I'd end up with a dangling pointer and Rust rightly won't let me.

How can I somehow tell the type system that I mean the returned Iterator::Item to be owned. Or perhaps I'm thinking about the problem in the wrong way? Any help would be much appreciated.

The code can be found here: GitHub - litriv/block-folder: A Rust iterator that consumes blocks of input, seperated by possibly multiple consecutive instances of some seperator.

I don't think you should expect BlockFolder::new(v.iter() to compile.

The iterator you're wrapping returns references, and you need aggregate values, and it's not possible to create new references out of thin air.

It should work with v.iter().copied().

Alternatively, you could try to make your aggregator type be something else, and require ToOwned or Clone bound on the iterator elements.

You should probably allow the fold function to be more generic and have a return type other than Self::Item. Look at how Iterator::fold() is implemented.

A less general solution specifically tailored to references and borrowing types in general would be to require Item: ToOwned and return Item::Owned instead.

Also note that your function can be vastly simplified if you include a mandatory initial value like Iterator::fold() does. This also lets your function take borrowed items, an owned accumulator, and return the same owned accumulator type: Playground

impl<I, B, D, F> Iterator for BlockFolder<I, B, D, F>
where
    I: Iterator,
    B: Clone,
    D: FnMut(&mut I::Item) -> bool,
    F: FnMut(B, I::Item) -> B,
{
    type Item = B;

    fn next(&mut self) -> Option<Self::Item> {
        let mut accum = None;

        loop {
            let Some(mut item) = self.iter.next() else { return accum; };

            if (self.delim_func)(&mut item) {
                if accum.is_none() {
                    continue;
                }

                return accum;
            }

            let lhs = accum.unwrap_or_else(|| self.initial.clone());

            accum = Some((self.fold_func)(lhs, item));
        }
    }
}

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.