Producing an iterator of slices from a slice

If I have a slice such as:

let my_slice = [1, 2, 3, 4];

how can I produce (using functional programming) an iterator that gives back the sequence of slices:

[1, 2, 3, 4]
[2, 3, 4]
[3, 4]
[4]
[]

Technically, my_slice is an array, not a slice. I’m assuming you’re talking about returning the presented sequences as (shared-reference) slices i.e. &[i32].

A straightforward approach would probably be to use a range and a map, i.e.

fn tails<T>(slice: &[T]) -> impl Iterator<Item = &[T]> {
    (0..=slice.len()).map(|i| &slice[i..])
}

fn main() {
    let my_array = [1, 2, 3, 4];
    let result = tails(&my_array);
    dbg!(result.collect::<Vec<_>>());
}
   Compiling playground v0.0.1 (/playground)
    Finished dev [unoptimized + debuginfo] target(s) in 3.77s
     Running `target/debug/playground`
[src/main.rs:8] result.collect::<Vec<_>>() = [
    [
        1,
        2,
        3,
        4,
    ],
    [
        2,
        3,
        4,
    ],
    [
        3,
        4,
    ],
    [
        4,
    ],
    [],
]

(playground)

Edit: There might be some minor advantages to using (0..slice.len()+1) instead of (0..=slice.len()). E.g. the latter does not implement ExactSizeIterator; also the former has a more performant .next() implementation. AFAIK slice length is always maximally isize::MAX as usize anyway, so the +1 cannot overflow.

5 Likes

Thanks! I was trying to put a solution together with scan, but this is much more elegant.

Just for fun, here's another way you could implement it:

use std::iter::successors;

fn tails<T>(slice: &[T]) -> impl Iterator<Item = &[T]> {
    successors(Some(slice), |s| s.get(1..))
}
8 Likes

Well, I think that just edges out as slightly more elegant than @steffahn's solution, but they were first so I'll leave that one marked as the solution :slight_smile:

Note that iter::successors and iter::from_fn can appear clean, but they have the downside of being able to know less about how many items will come out of the iterator.

The Range+Map version will be TrustedLen, for example. And because it'll have a useful size_hint -- successors will always just say "well it's at least zero and at most infinity items" -- things like collecting it will not need to reallocate as it'll reserve the right number of slots up front. Not to mention that it could be -> impl DoubleEndedIterator<Item = &[T]> without any other changes.

So I support mbrubeck's phrasing of "just for fun" for this case -- because the range+map version is itself pretty easy, you probably should use that one.

(iter::successors and iter::from_fn are better fits for complicated iterators where phrasing them as adapters would be hard, or where you don't have enough information to have good predictions anyway, like maybe if it's reading input from a user.)

I also like that the range+map version can be easily tweaked to not return the empty slice -- the successors version becomes much less elegant if you add that requirement.

7 Likes

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.