Implement a pairwise iterator

Question

I have trouble writing code for a function that takes an iterator and returns an iterator that iterates in pairs (Option<T>, T) like so

a = [1,2,3]
assert pairwise(a) == `[(None, 1), (Some(1), 2), (Some(2), 3)]

fn pairwise<I, T>(&xs: &I) -> I
where
    I: Iterator<Item = T>,
{
    [None].iter().chain(xs.iter().map(Some)).zip(xs.iter())
}

fn main() {
    let data: Vec<i32> = vec![1, 2, 3];
    let newdata: Vec<Option<i32>, i32> = pairwise(&data).collect();
    println!("{:?}", newdata);
}

error[E0599]: no method named `iter` found for type `I` in the current scope
 --> src/main.rs:3:28
  |
3 |     [None].iter().chain(xs.iter().map(Some)).zip(xs.iter())
  |                            ^^^^
  |

Not sure why xs isn't iterable. I've stated it in the where clause haven't I?

.iter() is for creating an iterator, but you've already got one. xs is already an Iterator. — loganfsmyth
– loganfsmyth, Commented Oct 2, 2017 at 22:44
@loganfsmyth Oh, okay. What is the type for something that has .iter() method? — user1685095
– user1685095, Commented Oct 2, 2017 at 22:45
I don't believe there is one. There is however an IntoIterator which defines the into_iter() method. This is automatically implemented for all Iterators, so if you have an API that takes an IntoIterator and you don't want to actually consume the argument, the caller can just call .iter() themselves and pass in the resulting iterator. — Lily Ballard
– Lily Ballard, Commented Oct 2, 2017 at 23:22

Shepmaster · Accepted Answer · 2020-02-03 18:55:02Z

6

fn pairwise<I, T>(&xs: &I) -> I

This doesn't make sense. See What is the correct way to return an Iterator (or any other trait)? and What is the difference between `e1` and `&e2` when used as the for-loop variable?.

I: Iterator<Item = T>,

There's no reason to specify that the Item is a T.

[None].iter()

It's better to use iter::once.

xs.iter()

There's no trait in the standard library that defines an iter method. Perhaps you meant IntoIterator?

let data: Vec<i32> = vec![1, 2, 3]

There's no reason to specify the type here; i32 is the default integral type.

Vec<Option<i32>, i32>
Vec<Option<i32>, i32>> // original version

This is not a valid type for Vec, and your original form doesn't even have balanced symbols.

After all that, you are faced with tough choices. Your example code passes in an iterator which has references to the slice but you've written your assertion such that you expect to get non-references back. You've also attempted to use an arbitrary iterator twice; there's no guarantee that such a thing is viable.

The most generic form I see is:

use std::iter;

fn pairwise<I>(right: I) -> impl Iterator<Item = (Option<I::Item>, I::Item)>
where
    I: IntoIterator + Clone,
{
    let left = iter::once(None).chain(right.clone().into_iter().map(Some));
    left.zip(right)
}

fn main() {
    let data = vec![1, 2, 3];

    let newdata: Vec<_> = pairwise(&data).collect();
    assert_eq!(newdata, [(None, &1), (Some(&1), &2), (Some(&2), &3)]);

    let newdata: Vec<_> = pairwise(data.iter().copied()).collect();
    assert_eq!(newdata, [(None, 1), (Some(1), 2), (Some(2), 3)]);
}

2 Comments

user1685095 Over a year ago

Thanks a lot. I think I don't understand only one thing. Why is Box needed here?

Lukas Kalbertodt Over a year ago

@user1685095 The linked question "What is the correct way to return an Iterator?" answers this question.

Marcel · Accepted Answer · 2021-12-15 20:02:02Z

3

~~I know OP asked for "outer pairwise" ([(None, 1), (Some(1), 2), (Some(2), 3)]), but here is how I adapted it for "inner pairwise" ([(1, 2), (2, 3)]):~~

~~fn inner_pairwise<I>(right: I) -> impl Iterator<Item = (I::Item, I::Item)> where I: IntoIterator + Clone, { let left = right.clone().into_iter().skip(1); left.zip(right) }~~

For anyone here for "inner pairwise", you're looking for Itertools::tuple_windows.

edited Dec 15, 2021 at 20:02

answered Dec 15, 2021 at 19:56

Marcel

1,2411 gold badge19 silver badges37 bronze badges

2 Comments

Shepmaster Over a year ago

I believe that's Itertools::tuple_windows

Marcel Over a year ago

It is, silly me.

Collectives™ on Stack Overflow

Implement a pairwise iterator

2 Answers 2

2 Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related