Issue #17016 has been updated by parker (Parker Finch).


Eregon (Benoit Daloze) wrote in #note-6:
> Maybe `prefix_sum` or just `prefix` or something like that would work?
> Having `sum` in it is kind of confusing though as it can be any "operation" not just `+`-ing numbers, but it seems an official "term" for it (https://en.wikipedia.org/wiki/Prefix_sum#Scan_higher_order_function).


I agree that including "sum" in the name is confusing. I think that "prefix_sum" is just used to describe the sum operation, and if it is generalized to other operations then it is typically called "scan".

-----


Eregon (Benoit Daloze) wrote in #note-9:
> 
> Using the existing lazy `map` seems most natural to me:
> ```ruby
> val = 0
> p (0..).lazy.map { |x| val += x }.first(4) # => [0, 1, 3, 6]
> 
> val = 0
> p [0] + (1..).lazy.map { |x| val += x }.first(3) # => [0, 1, 3, 6]
> ```

It's definitely possible to use `map`! I think it is simpler to use a scan, especially if the first element needs to be included in the lazy enumerator. For example:
```ruby
(1..).lazy.scan(0, &:+)
```
would need to be:
```ruby
val = 0
[val].chain((1..).lazy.map { |x| val += x })
```
because the `+` method doesn't work with lazy enumerators.

----------------------------------------
Feature #17016: Enumerable#scan_left
https://bugs.ruby-lang.org/issues/17016#change-86546

* Author: parker (Parker Finch)
* Status: Open
* Priority: Normal
----------------------------------------
## Proposal

Add a `#scan_left` method to `Enumerable`.

(The name "scan_left" is based on Scala's scanLeft and Haskell's scanl. It seems like "scan_left" would be a ruby-ish name for  this concept, but I'm curious if there are other thoughts on naming here!)

## Background

`#scan_left` is similar to `#inject`, but it accumulates the partial results that are computed. As a comparison:
```
[1, 2, 3].inject(0, &:+) => 6
[1, 2, 3].scan_left(0, &:+) => [0, 1, 3, 6]
```

Notably, the `scan_left` operation can be done lazily since it doesn't require processing the entire collection before computing a value.

I recently described `#scan_left`, and its relationship to `#inject`, more thoroughly in [this blog post](https://medium.com/building-panorama-education/scan-left-a-lazy-incremental-alternative-to-inject-f6e946f74c00).

## Reasoning
We heavily rely on the scan operation. We use an [event-sourcing](https://martinfowler.com/eaaDev/EventSourcing.html) pattern, which means that we are scanning over individual "events" and building up the corresponding state. We rely on the history of states and need to do this lazily (we stream events because they cannot fit in memory). Thus the scan operation is much more applicable than the inject operation.

We suspect that there are many applications that could leverage the scan operation. [This question](https://stackoverflow.com/questions/1475808/cumulative-array-sum-in-ruby) would be more easily answered by `#scan_left`. It is a natural fit for any application that needs to store the incrementally-computed values of an `#inject`, and a requirement for an application that needs to use `#inject` while maintaining laziness.

## Implementation
There is a Ruby implementation of this functionality [here](https://github.com/panorama-ed/scan_left/) and an implementation in C [here](https://github.com/ruby/ruby/pull/3078).

## Counterarguments
Introducing a new public method is committing to maintenance going forward and expands the size of the Ruby codebase -- it should not be done lightly. I think that providing the functionality here is worth the tradeoff, but I understand any hesitation to add yet more to Ruby!

---Files--------------------------------
scan_left_example.rb (2.93 KB)


-- 
https://bugs.ruby-lang.org/

Unsubscribe: <mailto:ruby-core-request / ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>