Scan is overly specialized

[mydogisbox]

Here is the existing type signature for std::iter::scan:
fn scan<St, B, F>(self, initial_state: St, f: F) -> Scan<Self, St, F> where F: FnMut(&mut St, Self::Item) -> Option<B>,

If I were to use a verbose name for scan as implemented now, I would call it map_with_state_until, this means that if I just want map_with_state, things can get really awkward using the existing scan if I want to return an option which doesn't terminate the Iterator for collect etc. e.g. vecter.iter().scan( |state, x| if x > 1 then Some(None) else Some(Some(x)) ).flatten()

If we instead have F just turn B instead of Option<B> like:
fn scan<St, B, F>(self, initial_state: St, f: F) -> Scan<Self, St, F> where F: FnMut(&mut St, Self::Item) -> B, then that becomes a lot more simple:
vecter.iter().scan( |state, x| if x > 1 then None else Some(x) )

and achieving the existing scan behavior is trivially achieved by simply adding fuse().

This allows scan to have behavior more in-line with similar functions like map and fold:

fn fold<B, F>(self, init: B, f: F) -> B where
    F: FnMut(B, Self::Item) -> B, 

fn map<B, F>(self, f: F) -> Map<Self, F> where
    F: FnMut(Self::Item) -> B,

and also brings it more in-line with how other languages define scan : (a -> b -> a) -> a -> [b] -> [a] (Haskell), ('State -> 'T -> 'State) -> 'State -> seq<'T> -> seq<'State> (F#) etc.

I think this also gives a clear way forward to addressing other issues which previously ended up unresolved like:
#14425

So I think there ought to be scan as defined above, and scan_until which is the existing implementation.

References:
http://zvon.org/other/haskell/Outputprelude/scanl_f.html

https://msdn.microsoft.com/en-us/visualfsharpdocs/conceptual/seq.scan%5b't,'state%5d-function-%5bfsharp%5d

[jonas-schievink]

We cannot change the existing definition of scan, but maybe adding another method makes sense, provided that this is useful enough.

[RustyYato]

Isn't map_with_state just map? I don't see what the difference is given that Rust has stateful closures. scan takes an iterator and can arbitrarily change how many elements are yielded (which no other adapter does, and may be too powerful and unweildy). This makes it useful in some niche cases.

[mydogisbox]

@KrishnaSannasi

can arbitrarily change how many elements are yielded

This is exactly the part of the existing scan implementation which I think is problematic. Its non-standard to not yield an output element for each input element (see https://en.wikipedia.org/wiki/Prefix_sum for the generally accepted definition). This makes it less generally applicable than otherwise.

You can certainly implement the standard scan definition using map and a stateful closure, but its much less obvious what is happening and requires application developers to implement more logic. scan is a standard function in most modern languages.

In my case I'm laying out lines of text with word wrapping so I need to keep track of the y-offset of the end of the previous line and yield the character offset of where to split each line. The wikipedia article I linked lists other applications.

[mydogisbox]

Building on the naming in the wikipedia article, maybe we could add inclusive_scan and exclusive_scan and deprecate scan.

[0-Kala-0]

If we look at the different map and fold methods that exist, we can infer how scan methods should behave and be named.

Mapping methods

Regular mapping :

fn map<B, F>(self, f: F) -> Map<Self, F>
where
    F: FnMut(Self::Item) -> B

Filter mapping (F returns an Option<B>. When encountering None, the value is skipped and the mapping goes on):

fn filter_map<B, F>(self, f: F) -> FilterMap<Self, F>
where
    F: FnMut(Self::Item) -> Option<B>

While Mapping (F returns an Option<B>. When encountering None, the mapping ends):

fn map_while<B, P>(self, predicate: P) -> MapWhile<Self, P>
where
    P: FnMut(Self::Item) -> Option<B>

Folding methods

Seeded folding:

fn fold<B, F>(self, init: B, f: F) -> B
where
    F: FnMut(B, Self::Item) -> B

First-seeded folding:

fn fold_first<F>(self, f: F) -> Option<Self::Item>
where
    F: FnMut(Self::Item, Self::Item) -> Self::Item

---

A scan is literally meant to map each step of a folding operation. As it's somehow a combination of both operations, the concept of "scanning" might be any combination of their variants. If we stick to consistency in the naming, the possible scanning methods would be :

	Seeded	First as seed
Regular	fn scan<St, B, F>(self, initial_state: St, f: F) -> Scan<Self, St, F> where F: FnMut(&mut St, Self::Item) -> B	fn scan_first<F>(self, f: F) -> ScanFirst<Self, F> where F: FnMut(Self::Item , Self::Item) -> Self::Item
Filter	fn filter_scan<St, B, F>(self, initial_state: St, f: F) -> Scan<Self, St, F> where F: FnMut(&mut St, Self::Item) -> Option<B>	fn filter_scan_first<F>(self, f: F) -> FilterScanFirst<Self, F> where F: FnMut(Self::Item, Self::Item) -> Option<Self::Item>
While	fn scan_while<St, B, F>(self, initial_state: St, f: F) -> Scan<Self, St, F> where F: FnMut(&mut St, Self::Item) -> Option<B>	fn scan_first_while<F>(self, f: F) -> ScanFirstWhile<Self, F> where F: FnMut(Self::Item, Self::Item) -> Option<Self::Item>

(note that I'm not 100% certain that the _first versions actually need to require a function returning a Self::Item. They might be implemented requiring functions returning any B with a Self::Item accmulator internally, but it's non-trivial and I've done enough research one today ^^)

We can see from this table that the current behavior of scan is the behavior we could expect of scan_while(). It's made even more obvious by the observation that map_while() is just a particular case of the current implementation of scan() (where you just ignore the accumulator) : #68537 (comment).

It is indeed very hard to change the current definition of scan as it would completely break existing code. Changing the naming convention could be the way to get around the problem (and indeed depreciating scan()). Additionally, if we want to keep some form of consistency, it would also be needed to change the name of fold() (and depreciate the current one). Here's a proposal :

fold_seed() // currently: fold()
fold_first() // currently: fold_first(), no change here

scan_seed() // no method in rust
scan_first() // no method in rust

filter_scan_seed() // no method in rust
filter_scan_first() // no method in rust

scan_seed_while() // currently: scan()
scan_first_while() // no method in rust

Obviously, not all of them are not needed. Some of them can be easily expressed using other ones (see the Wikipedia article above for details). Some of them have very few practical use and might not need to be implemented in Rust.

Though, I strongly agree with the original concern of the issue : having as the only available implementation of scan the one we currently have is quite terrible : more often than not, the "end scanning when F returns None" behavior is unrevelant for the current use case and sometimes it's even getting in the way of what's being done, resulting in quite unreadable code like the one described by @mydogisbox or even worst if you're trying to achieve a filter_scan().

PS : I'm not sure how "seeded" and "first-seeded" relate to "inclusive" and "exclusive" scanning/folding. It seems to me that they're different concepts, and the Wikipedia page seems to disagree with me but in a very unclear way, so I chose not to confuse the two. They might be the same thing, IDK

[mydogisbox]

@Mayt38 great points!

I was trying to implement a function which accepts an iterator and reduces adjacent repeating elements into only one element. Say we have [1, 1, 2, 3, 4, 4, 5], and I want the output to be [1, 2, 3, 4, 5]. I found that I had to resort to the nested Option solution. I really think that it is a great point that we should have scan not fusing the iterator. The current implementation violates the Single Responsibility Rule and really leads to confusion in that it behaves different from the common scan's as in other languages.

[Johannesd3]

Besides the fact that the current scan should actually be called scan_filter, I don't like that the closure takes a mutable reference. Aren't iterators all about avoiding mutability?

The proposed scan (without _while) would be equivalent to

let mut state = init;
iter.map(move |x| f(state, x));

This is at least as simple and pretty as scan (map and its closure both take one argument while scan and its closure require two arguments which might get ugly), and more importantly, it doesn't hide the fact that there is some kind of mutability. Maybe that's a reason why a "simple" scan never made it to the standard library. However, after introducing map_while, the current scan could also be replaced in this way. In my opinion, scan becomes quite useless.

Let's consider Haskell's scanl. It is very similar to folding but it preserves all intermediate accumulator states and creates a new list of it. Implementing this in Rust gets more complicated.

First try:

let mut state = init;
iter.map(move |x| {
   state = f(state, x);
   state
}))

...but this does only work for copy types and it differs from Haskell's scanl: The first item of scanl's resulting list is always the init element (so that it has one more item than the original list).

My next try, now passing the state to f by reference:

let mut state = init;
iter.map(move |x| {
   let new_state = f(&state, x);
   std::mem::replace(&mut state, new_state)
})

...but now the last item is missing and we cannot simply get it out of the closure's state. Unless anyone else has a better idea, you would have to create your own iterator struct to emulate the behaviour of Haskell.

Haskell is a well-thought-out language and I think that scanl is useful, in contrary to Rust's current scan. So if you consider deprecating and replacing scan, you might as well take these thoughts into consideration.

[mydogisbox]

@Johannesd3 I didn't even think about how odd it is to have the state being mutable. Good point.

[RustyYato]

Aren't iterators all about avoiding mutability?

I disagree with this, iterators are about being declarative instead of imperative, mutability is an orthogonal concern. Rust doesn't shy away from mutability like in more functional languages, because sometimes mutability is required for performance or making the algorithm easier to understand. Limiting mutability artificially makes apis harder to use in Rust.

For example: Vec::retain could give you &mut T, but it doesn't, it gives you a &T. This makes it painful to use. So painful, that other Vec-like abstractions changed their retain to give a &mut T (SmallVec::retain). This will eventually be "fixed" by drain_filter, which does give you a &mut T, whenever that stabilizes. Because of this, I don't believe chasing after immutability, when it is easy to allow mutability is useful.

All that said, I also agree that the current implementation of Scan is pretty niche and not fit for std.

Let's consider Haskell's scanl. It is very similar to folding but it preserves all intermediate accumulator states and creates a new list of it. Implementing this in Rust gets more complicated.

scan is useless in Rust precisely because Rist has mutability, and is useful in Haskell precisely because it lacks mutability. In Rust map can do pretty much everything that scanl does in Haskell, so it doesn't seem useful to have an additional scan functionality. Mutability isn't bad, unconstrained mutability is bad, and Rust provides the tools to constrain mutability without making it useless.

scanl in Rust

-- from prelude
scanl :: (b -> a -> b) -> b -> [a] -> [b]

is equivalent to

mut_scanl :: (a -> State b ()) -> b -> [a] -> [b]
mut_scanl mut_f b as = scanl f b as
    where f b a = next_b
            where ((), next_b) = runState (mut_f a) b

is equivalent to the following Rust

fn scanl<B, F, I>(f: F, mut b: B, iter: I) -> impl Iterator<Item = B>
where
    I: Iterator,
     // in Haskell everything is `Clone`, so this is equivalent
    B: Clone,
    // 1. may as well provide `FnMut` because we can
    // 2. `&mut B` is equivalent to `State B ()` in Haskell
    F: FnMut(I::Item, &mut B),
{
    iter.map(move |a| {
        f(a, &mut b);
        b.clone()
    })
}

We could take it a step further:

fn scanl<B, F, I>(f: F, mut b: B, iter: I) -> impl Iterator<Item = C>
where
    I: Iterator,
    F: FnMut(I::Item, &mut B) -> C,
{
    iter.map(move |a| f(a, &mut b))
}

But what does this offer over map? Since map already gives you &mut _ access to you surrounding scope, this scanl gives you no additional power.

I can see a use case for the first implementation of scanl in Rust: When you want to partition your state and return a portion of it, but even that first version of scanl seems super niche.

We transform this back to Haskell too

mut_scanl :: (a -> State b c) -> b -> [a] -> [c]
mut_scanl mut_f b = join . map pick_c . scanl f (b, Nothing)
    where f (b, _) x = (next_b, Just next_c)
            where (next_c, next_b) = runState (mut_f x) b
          pick_c (_, c) = maybeToList c

(my Haskell isn't great, I'm just trying so the actual implementations aren't the focus, just the signatures)

[Johannesd3]

I wasn't claiming that scanl in Rust would be super useful. But I think it is at least more useful than the current scan.

One example: Creating an iterator that yields factorials using num_bigint.

Using scan:

iter::once(one()).chain((1..).scan(one(), |state: &mut BigUint, x: usize| {
    *state *= x;
    Some(state.clone())
}))

Using map makes this not worse in my opinion:

let mut fac = one();

(0..).map(move |n: usize| { 
    if n > 0 { 
        fac *= n;
    }
    fac.clone()
})

And using a Haskell-like myscan:

myscan(1.., one(), |state: &BigUint, x: usize| x * state)

Link to playground, containg the implementation of myscan.

But the last one has two disadvantages: 1. The next factorial is calculated one step too early. 2. It is noticeably slower, but I am not sure why.

So at least there seems to be a reason why the way with the mutable reference was chosen. (However, I am curious what exactly makes it so much slower, even though it works without clone)

EDIT: Wrong link

[mydogisbox]

@RustyYato the more general scan is useful in rust when you want to chain iterator functions like (actual example from my code):

    font.layout(todo, *scale, point)
        .enumerate()
        .scan(0., |row_offset, (index, item)| {
            let item_offset = item
                .pixel_bounding_box()
                .map_or_else(|| item.position().x, |x| x.max.x as f32);
            if index == 0 {
                Some(Some(0))
            } else if item_offset - *row_offset <= (WIDTH as f32) {
                Some(None)
            } else {
                *row_offset = *row_offset + item_offset;
                Some(Some(index))
            }
        })
        .flatten()
        .chain(once(todo.len()))
        .collect::<Vec<usize>>()
        .windows(2)
        .map(|indices| &todo[indices[0]..indices[1]])
        .collect::<Vec<&'a str>>()

In this example using map with a mutable collection would be much less readable than using scan due to how it changes the scope of what is needed to understand a particular step in the chain.

retain seems like a poor example for why mutability would be a good thing generally since its an inherently mutating operation in the first place, whereas map, scan etc are not.

I'm not against mutability, but I do think that separating mutable operations from non-mutable operations improves readability because expectations are more clear. If I wanted to both transform each element and update a collection I would just use a for loop. This is how its done in other languages I've used that have mutability controls (e.g. F#).

Whether this is done conventionally or enforced by the standard library definitions is, however, a different question. Maybe there is a case to be made that people ought to be allowed to mutate at will for performance or other reasons.