Map with accumulator on an array

2.2k views Asked by At

I'm looking to create a method for Enumerable that does map and inject at the same time. For example, calling it map_with_accumulator,

[1,2,3,4].map_with_accumulator(:+)
# => [1, 3, 6, 10]

or for strings

['a','b','c','d'].map_with_accumulator {|acc,el| acc + '_' + el}
# => ['a','a_b','a_b_c','a_b_c_d']

I fail to get a solution working. I think I can do it with reduce. I was working down the path of something like:

arr.reduce([]) {|acc,e| ..... }

with the initial value being an empty array, but I couldn't get it correct.

edit: See Jörg's answer below for a proper solution. Another (somewhat gross) way to do it I realized after reading his answer is by using instance_eval, which changes the context of the given block to that of the object executing it. So self is set to reference the array rather than the calling context (which means it is no longer a closure!) and inject and shift are called by the array. Convoluted, unnecessarily terse, and confusing to read, but it taught me something new.

['a','b','c','d'].instance_eval do
  inject([shift]) {|acc,el| acc << acc.last+el}
end
#=> ['a','ab','abc','abcd']
3

There are 3 answers

1
Jörg W Mittag On BEST ANSWER

This operation is called scan or prefix_sum, but unfortunately, there is no implementation in the Ruby core library or standard libraries.

However, your intuition is correct: you can implement it using Enumerable#inject. (Actually, Enumerable#inject is general, every iteration operation can be implemented using inject!)

module Enumerable
  def scan(initial)
    inject([initial]) {|acc, el| acc << yield(acc.last, el) }
  end
end

[1,2,3,4].scan(0, &:+)
# => [0, 1, 3, 6, 10]

%w[a b c d].scan('') {|acc, el| acc + '_' + el }
# => ["", "_a", "_a_b", "_a_b_c", "_a_b_c_d"]

Ideally, the behavior should match that of inject with its 4 overloads (in which case it would give you the results you specified), but unfortunately, implementing those overloads in Ruby, without privileged access to the VM internals (in particular, the arguments at the send site) is a major pain in the rear section.

It goes something like this:

module Enumerable
  # Trying to match the signature of `inject` without access to the VM internals
  # is a PITA :-(
  def scan(initial=(initial_not_given = true; first), meth=nil)
    raise ArgumentError, 'You can pass either a block or a method, not both.' if block_given? && meth
    return enum_for(__method__) if initial_not_given && !meth && !block_given?
    return enum_for(__method__, initial) unless initial.is_a?(Symbol) || meth || block_given?
    meth, initial, initial_not_given = initial, first, true unless initial_not_given || meth || block_given?
    raise ArgumentError, "Method #{meth.inspect} is not a Symbol." unless meth.is_a?(Symbol) || block_given?

    this = if initial_not_given then drop(1) else self end

    return this.inject([initial]) {|acc, el| acc << acc.last.__send__(meth, el) } unless block_given?
    this.inject([initial]) {|acc, el| acc << yield(acc.last, el) }
  end
end

[1,2,3,4].scan(:+)
# => [1, 3, 6, 10]

%w[a b c d].scan {|acc, el| acc + '_' + el }
# => ["a", "a_b", "a_b_c", "a_b_c_d"]

As you can see, the implementation in terms of inject itself is rather elegant, the ugliness is solely due to implementing overloading in a language without overloading.

0
John La Rooy On

Here is a way using reduce

['a','b','c','d'].reduce([]){|acc, e| acc << (acc == []?e:acc.last+'_'+e)}
2
Cary Swoveland On

You could do that as follows:

module Enumerable
  def map_with_accumulator(sym)
    each_with_object([]) do |e,arr|
      arr <<
        if block_given?
          arr.empty? ? yield(first) : arr.last.send(sym, yield(e))
        else
          arr.empty? ? e : arr.last.send(sym,e)
        end
    end
  end
end

[1,2,3,4].map_with_accumulator(:+)             #=> [1,  3,  6, 10] 
[1,2,3,4].map_with_accumulator(:-)             #=> [1, -1, -4, -8] 
[1,2,3,4].map_with_accumulator(:*)             #=> [1,  2,  6, 24] 
[1,2,3,4].map_with_accumulator(:/)             #=> [1,  0,  0,  0] 

[1,2,3,4].map_with_accumulator(:+, &:itself)   #=> [1,  3,  6, 10] 
[1,2,3,4].map_with_accumulator(:-, &:itself)   #=> [1, -1, -4, -8] 
[1,2,3,4].map_with_accumulator(:*, &:itself)   #=> [1,  2,  6, 24] 
[1,2,3,4].map_with_accumulator(:/, &:itself)   #=> [1,  0,  0,  0] 

[1,2,3,4].map_with_accumulator(:+) { |e| 2*e } #=> [2,  6, 12,  20] 
[1,2,3,4].map_with_accumulator(:-) { |e| 2*e } #=> [2, -2, -8, -16] 
[1,2,3,4].map_with_accumulator(:*) { |e| 2*e } #=> [2,  8, 48, 384] 
[1,2,3,4].map_with_accumulator(:/) { |e| 2*e } #=> [2,  0,  0,   0] 

[1,2,3,4].to_enum.map_with_accumulator(:+) { |e| 2*e } #=> [2,  6, 12,  20] 
(1..4).map_with_accumulator(:+) { |e| 2*e }            #=> [2,  6, 12,  20] 
{a: 1, b: 2, c: 3, d: 4}.map_with_accumulator(:+) { |_,v| 2*v }
  #=> [2,  6, 12,  20]