Crystal: Implement cumulative folding

[ghost]

Analog to reduce, but returns an Enumerable or Iterator containing the successive reduced values (e.g. running totals, maxima). The last element has the same value as reduce. Cumulative folding is also available in many other languages, see the following section:

naming

Cumulative folding goes by many different names in various languages and tools out there:

• c++: partial_sum, {in,ex}clusive_scan
• clojure: reductions
• d: cumulativeFold
• haskell: scanl
• matlab: cum{sum,min,max,prod}
• python itertools: accumulate
• rust: scan
• compsci: prefix sums (running totals)

Using the plurals of functions included in the stdlib is merely a suggestion. Futhermore, scan is already associated with string scanning.

usage examples

# running max:
[1,4,2,5,3].reduce     { |a, b| {a, b}.max } # => 5
[1,4,2,5,3].reductions { |a, b| {a, b}.max } # => [1, 4, 4, 5, 5]

[4,2,4].reduce     64 { |a, b| a // b } # => 2
[4,2,4].reductions 64 { |a, b| a // b } # => [16, 8, 2]

# also lazy iterations:
(1..).reductions { |a, b| a + b }.first(5).to_a # => [1, 3, 6, 10, 15]

# running sums; convenience variant of reductions, analog to sum vs reduce:
[1,2,3,4,5].sum  # => 15
[1,2,3,4,5].sums # => [1, 3, 6, 10, 15]

[1,2,3,4,5].sum  100 # => 115
[1,2,3,4,5].sums 100 # => [101, 103, 106, 110, 115]

# running products:
[1,2,3,4,5].product  # => 120
[1,2,3,4,5].products # => [1, 2, 6, 24, 120]

Do we also want maxima, minima as analog to min and max or would these be regarded as too obscure for the stdlib?

motivational examples

Advent of Code 2018, Day 01, Part 2

Task: Add up numbers from file and detect first duplicate in running sums.

Similar implementations by Ary and Linus.

freqs = File.read_lines("input").map &.to_i

...

accm = 0
seen = Set{accm}
freqs.cycle.each do |x|
  accm += x
  return accm unless seen.add? accm
end

# could be reduced to:

seen = Set{0}
freqs.cycle.sums.find { |accm| !seen.add? accm }

Advent of Code 2015, Day 01, Part 2

Task: Parens as floor levels; starting at one, find first negative step.

Similar implementation by Ary.

instrs = File.read("input").chars.map { |p| p == '(' ? 1 : -1 }

...

accm = 0
instrs.each_with_index do |instr, idx|
  accm += instr
  return idx.succ if accm < 0
end

# could be reduced to:

instrs.sums.index(&.< 0).succ

[yxhuvud]

I'm skeptical about effectively doubling the amount of methods on Enumerable and Iterable. I wonder if a better solution would be to add some conventions or methods to inspect partial sums from the iterator itself or something.

[jhass]

I'm in favor of something like reductions but I think we can do away with all the others since reductions should allow to implement them quite easily when needed.

[asterite]

I think adding reductions, sums and products is fine, but maybe naming them cummulative_reduce, cummulative_sum and cummulative_product. It's not clear that sums means "cummulative".

These are just three methods. The cost of adding them is just a bit of parsing time and the AST in memory, for the method. If not used it has no impact in compilation. And the more generally useful methods we have in Enumerable, I think it's better.

Question: it seems sums changes semantic when called on Enumerator vs. Iterator, right? It seems to return an Iterator in the case of Iterator. I ask because otherwise freqs.cycle.sums would never finish executing.

[RX14]

I'm not sure reductions is popular enough to necessitate adding sums and products - we can start with just reductions and see if there is appetite/usecases for sums/products. So I like reductions and each_reduction.

[yxhuvud]

FWIW, Ruby is adding #produce in 2.7, where you can do stuff like

Enumerator.produce([0, 1]) { |base_1, base_2| [base_2, base_1 + base_2] }.take(10).map(&:first)
=> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

which may perhaps be a nice form and name (?) for this (with tuples if we can get it to work).

(see https://blog.saeloun.com/2019/11/27/ruby-2-7-enumerator-produce )

[ghost]

That's basically unfold, correct? How would you apply that to an array, for example?

[ryanprior]

Could reductions be a macro instead of another function? I think these things would be equivalent for example:

(1..10).reductions 0 { |sum, n| sum + n }
# can be written as
(1..10).reduce [0] { |sum, n| sum << sum.last + n }

I wouldn't hesitate to write the second form, it doesn't look ugly to me. Any drawbacks to that approach or to a macro providing slick syntax sugar for it?

[ghost]

Any drawbacks to that approach [...]?

What would a non-eager version look like?

Anyways, I'm closing this, no longer using crystal. Feel free to reopen if someone else feels like spearheading this.

[wontruefree]

What about adding one method to enumerable and then adding the other methods off that?
It would help limit the method space on Enumerable but it might complicate the implementation.

(1..10).cumulative.reduce 0 { |sum, n| sum + n }
(1..10).cumulative.products