Look Behind Iterator Borrowing the Current Value

1

I'd like to iterate over a collection, and during the iteration, have access to the value of the previous iteration. So I wanted to make an iterator that returned a pair of the current value and, if there is one, the previous value. Obviously if it returns the current value from next(), then that value will be consumed and can't be returned for the next loop, so the current value returned by next() has to be borrowed in some fashion. But I don't know exactly how to specify a borrowed value as the member of a struct. It says "missing lifetime specifier" but the "Pair" struct can't take a lifetime, since that would mean the Iterator implementation would have to take a lifetime, and that errors out with "the lifetime parameter 'a is not constrained by the impl trait, self type, or predicates" despite it being used by one of the predicates.

This is what I started with:

use std::env;

struct Pair where I: Iterator  {
    behind: Option,
    current: &I::Item,
}

struct LookBehind where I: Iterator {
    iter: I,
    current: Option
}

impl Iterator for LookBehind {
    type Item = Pair;
        
    fn next(&mut self) -> Option> {
        let behind = self.current;
        self.current = self.iter.next();
        match self.current {
            Some(ref item) =>
                match behind {
                    behind @ Some(_) => Pair {
                        behind: behind,
                        current: item
                    },
                    None => Pair {
                        behind: None,
                        current: item
                    }
                },
            None => None
        }
    }
}

fn lookbehind(iter: I) {
    return LookBehind{iter: iter, current: None}
}


fn main() {
    for pair in lookbehind(env::args().skip(1)) {
        println!("{} {}",pair.behind,pair.current)
    }
}

and this is when I specified the lifetime as required:

use std::env;

struct Pair<'a, I> where I: Iterator  {
    behind: Option,
    current: &'a I::Item,
}

struct LookBehind where I: Iterator {
    iter: I,
    current: Option
}

impl<'a, I: Iterator> Iterator for LookBehind {
    type Item = Pair<'a,I>;
        
    fn next(&mut self) -> Option> {
        let behind = self.current;
        self.current = self.iter.next();
        match self.current {
            Some(ref item) =>
                match behind {
                    behind @ Some(_) => Pair {
                        behind: behind,
                        current: item
                    },
                    None => Pair {
                        behind: None,
                        current: item
                    }
                },
            None => None
        }
    }
}

fn lookbehind(iter: I) {
    return LookBehind{iter: iter, current: None}
}


fn main() {
    for pair in lookbehind(env::args().skip(1)) {
        println!("{} {}",pair.behind,pair.current)
    }
}
2

It is correctly observed, than the Iterator can't lend out anything from itself. The iterator is only an intermediate between something that owns the data and the iteration.

With that restriction in mind, I think it makes sense to restrict this kind of iterator to only iterator elements that can be cloned. For numerical elements or where the iterator elements are references, this works out great. This way you can just keep a copy of the last element and yield it togther with the next.

3

Incidentally, I had a need for just such an iterator yesterday, and I used a different approach that might interest you. Here's a simplified version of my use case: using lookbehind to implement an equivalent of Vec::dedup.

There is probably an obvious reason why your approach is better, but I felt like using the std iterator building blocks gave me fewer opportunities to make mistakes, so I went with it.

fn uniq<E>(elems: &[E]) -> Vec<E>
    where E: Clone + PartialEq {
  // Create the "current element" iterator.
  let it = elems.into_iter();
  // Clone it into a second iterator which
  // 1. Produces Option<E> instead of E, and
  // 2. Yields a single None before the sequence.
  // This effectively timeshifts the original
  // iterator, giving us the lookbehind behavior.
  // Aside: I'm missing Haskell's `singleton`.
  let behind = repeat(None).take(1)
        .chain(it.clone().map(|e| Some(e)));
  // A sink for our selected elements.
  let mut out = Vec::new();
  // This loop could also be written using filter_map.
  // I wrote it as a for loop here to mirror your
  // original.
  for (prev, current) in behind.zip(it) {
    if prev != Some(current) {
      out.push(current.clone());
    }
  }
  out
}

I see two drawbacks with this approach -- three, if the iterator construction and manipulation feels unpleasant. :smile:

First, if you want to make it generic over any IntoIterator, instead of just slices, the type constraints are a little wordy. Here's what I came up with:

fn collapse<I, E, II>(elems: I) -> Vec<E>
  where I: IntoIterator<Item=E, IntoIter=II>,
        II: Iterator<Item=E> + Clone,
        E: Clone + PartialEq {
  ...
}

I would not enjoy documenting that.

Second, it doesn't lend itself well to returning the constructed iterator, simply because the types involved are scary. The type of the iterator returned by zip is

Zip<Chain<Take<Repeat<Option<E>>>, Map<II, fn(E) -> Option<E>>>, II>

But you could hide that inside a "newtype" struct and forward the Iterator methods through, if desired. (Aside: oh, for generalized newtype deriving.)

4

Fun! We actually have an approved rfc for std::iter::once, a singleton iterator, it just hasn't been implemented yet. (Until then we have Some(x).into_iter())

You can use associated types like this:

fn collapse<I>(elems: I) -> Vec<I::Item>
  where I: IntoIterator,
        I::Item: Clone + PartialEq,
        I::IntoIter: Clone,
{
  ...
}

And the itertools crate has its own implementation of an adaptor called .dedup() :wink:

5

Thanks for replying! Wow, I can't believe I didn't check back here for 300 days straight. FWIW, I thought up a neat way to do it that seems rather concise, using std::iter::fold. Assuming it's feasible to do your "look behind" logic inside a callback function, that is.

use std::env;

fn looking_behind(behind: Option<String>, current: String) -> Option<String> {
   match behind  {
     Some(behind) => println!(" then {} {}",behind,current),
     None => println!("first {}",current)
  };
   return Some(current);
}

fn main() {
   let nothing = env::args().skip(1).fold(None, looking_behind);
   match nothing  {
     Some(nothing) => println!("derp {}", nothing),
     None => println!("yay")
  };
}

You could even supply "" for the initial fold argument, and have fn(String,String) -> String.

1 Like