Asking for full break down/explanation of "reduce" method

Hi everybody.

I am struggling really hard to implement the ruby method “reduce”.
I am a bloody beginner in ruby and in one of my homework assignments on a website i wanted to learn ruby with, they asked me to implement the ruby method “reduce” all by myself.
I have struggled with this for a few hours now and i am getting really really annoyed because i cant find a simple break down on the internet and all i’ve tried so far is not working properly.

As i said, i am a beginner, so i don’t know all of the complex stuff ruby probably can do, but i know most of the simple things.
If anyone could please please take their time to break down the “reduce” method for me as simple as possible to them, that would be very, veeery awesome and would ease my frustration…

The assignment is set up like this:

Implement the ruby method reduce.
Reminder: Ruby reduces a list to a single value.
You mustn’t use “array.reduce” within this assignment.
The user should be able to choose the operator the method is reducing with with a block
Even if an empty list is given to your method it should return at least the initial value or something other than nil.
All of the following examples should work with your method:

reduce([1, 2, 3, 4], 0) { |sum, element| sum + element } # => 10

reduce(1…4, 0) { |sum, element| sum + element } # => 10

reduce([“a”, “b”, “c”, “d”], “”) { |sum, element| sum + element } # => “abcd”

def select(list)
reduce(list, []) do |new_ary, element|
if yield element
new_ary << element
end
new_ary
end
end

select([1, 2, 3, 4]) { |element| element.even? } # => [2, 4]

I hope someone will reply to this and excuse me if anything is hard to understand, english is not my native tongue.

It sounds like I’m no more expreienced than you with Ruby but have been coding for decades, maybe this will help.
Given a list, which could be an array or range or even a hash, step through all the elements of the list applying the operation or test given to each element and accumulating the results.
All of the examples use a block and I suspect ‘yield’ is the output of the block to accumulate.
I also found this out on the web:

  def map(&block)
    result = []
    each do |element|
      result << block.call(element)
    end
    result
  end
Look into Enumerable.reduce and Enumerable.inject which are synomynous(the same) but might give slightly different views of the definition.
When writing a menu class I found that method(:someMethod) allowed the method to be called from the menu. That might apply here.
Perhaps if you were to show what you've tried and what specifically has you stopped you might get more help.
I did a search of "Ruby method reduce" and found that helpful.
Personally I'm interested in where you found the website with this assignment.
Ciao,
Mike

Hi @rubynewbee

First of all: Thank you already for helping me xD
The website is a german one, so if you aren’t able to speak german, it won’t be helpful to you, they don’t translate most of what they are doing. Just in case you are german too or want to check it out either way, this is the website:

https://open.hpi.de/courses/ruby2018

And for what i have tried so far, this was my first attempt:

def reduce(list, initial)
list.each do |x| initial += x end
return initial
end

reduce([1, 2, 4], 0)

but the yield is missing in there and from there on i just tried to use yield but i just dont get how i can make it so that all the operations for my small code snippet can be chosen by the block.

this was my second attempt:

def reduce(list, initial)
sum = 0
list.each do |x|
yield(sum, initial, x) end
end

reduce([1, 2, 4], 0) {|sum, initial, x| sum += initial += x }
reduce([1, 2, 4], 0) {|sum, initial, x| sum -= initial -= x }

this one isn’t working either… and i tried so many things but then i came to the conclusion that all operators have to be chosen in my way of doing it
if i try to use “sum += the rest” then the result would be wrong if i intended to substract while reducing and not add, which i would need to choose with the block.

If my explanation is confusing i will try my best to rephrase it xD

To begin with I’ve not found your English wanting, rather very clear.
I looked at the site of your lessons and 2 semesters of conversational German 50 years ago wasn’t enough for me to make it through the first paragraph.

In the Enumerable module’s definition of reduce I see this:
%q/
reduce(initial, sym) -> obj click to toggle source
reduce(sym) -> obj
reduce(initial) {| memo, obj | block } -> obj
reduce {| memo, obj | block } -> obj

Combines all elements of enum by applying a binary operation,
specified by a block or a symbol that names a method or operator.

If you specify a block, then for each element in enum the block is
passed an accumulator value (memo) and the element. If you specify
a symbol instead, then each element in the collection will be passed
to the named method of memo. In either case, the result becomes the new value for memo. At the end of the iteration, the final value of
memo is the return value for the method.

If you do not explicitly specify an initial value for memo, then
uses the first element of collection is used as the initial value of
memo.

Examples:
#Sum some numbers
(5…10).reduce(:+) #=> 45
Same using a block and inject
(5…10).inject {|sum, n| sum + n } #=> 45
#Multiply some numbers
(5…10).reduce(1, :*) #=> 151200
# Same using a block
(5…10).inject(1) {|product, n| product * n } #=> 151200
# find the longest word
longest = %w{ cat sheep bear }.inject do |memo,word|
memo.length > word.length ? memo : word
end
longest #=> “sheep”
/

From this I conclude that reduce will take as parameters a list,
an initial value and a symbol (for an operator or a method) or a block.

My version, so far, after many tries:
def reduce(list, initial=0, sym, &block)
if sym and sym.class == Symbol
list.each{ |i| initial = initial.send(sym,i) }
else
list.each{ |i| initial = block.call(initial, i) }
end
initial
end

irb> n => [1, 2, 3, 4, 5]
irb> reduce(n,1,:) => 120
irb> reduce(1…5,1,:
) => 120
irb> reduce([1,2,3,4,5],1,:*) => 120
irb> reduce([1,2,3,4,5],0,:+) => 15
irb> reduce([1,2,3,4,5],5,:- ) => -10
irb> reduce([1,2,3,4,5],1.0,:/) => 0.008333333333333333
irb> [1,2,3,4,5].reduce(1.0,:/) => 0.008333333333333333
Note here I’m using Ruby’s reduce to check my work.
irb> alias inject reduce
irb> [1,2,3,4,5].inject(1.0,:/) => 0.008333333333333333

irb> c => [“a”, “b”, “c”, “d”, “e”]
irb> reduce(c,’’,:+) => “abcde”
irb> reduce(‘a’…‘e’,’’,:+) => “abcde”

While this works for symbols I’ve yet to get it working for a block.
Sigh.
I should point out that since you used ‘list’, I did too but we both
need to quit that since Ruby has no lists only strings, arrays, ranges
and hashes.

Here is a site that will answer all our questions about reduce:
https://mauricio.github.io/2015/01/12/implementing-enumerable-in-ruby.html
Mauricio lays it all out just as if he were teaching a class. It’s going to take me a while to understand it all.

BTW, is ‘xD’ a wink and a smile? I’ve not seen that before.

This exercise has certainly helped me as I hope it has you.
Be well,
Mike

Wow! hank you very very much for your time!

The smiley is :laughing: this one, usually it is used if something is very funny, i also use it, if something is uncomfortable (like my possible lack of english communication skills) or if i feel like spicing up the sentence. it is a weird habbit and i just noticed that…

I still need to go over your text to fully understand it, but it is very informative, again thank you very much for helping me out!

Hi Tiamasa,
You’re quite welcome for the help and for one using a second language I think you are doing quite well. I’m certainly having no trouble understanding you.
Challenges like this sometimes just won’t let go. I woke up at 3:00AM with this running through my head and finally got up at 4AM to try again. I went back to Ruby’s version of Array.reduce trying to find a block that would work with that. This site gave me some insite:
https://mixandgo.com/learn/mastering-ruby-blocks-in-less-than-5-minutes. With that for help I finally managed to get a block to work with Ruby’s reduce like this:
irb> evens = n.reduce([]){ |memo,i| memo << i if i.even?; memo }
=> [2, 4]
My version still didn’t work, grr, but Mauricio had a version that used just a block so I tried that with the same block and it performed nicely. With that in mind I stripped my version down to just use a block and found it too worked. This suggested there was something wrong with the ‘if’ statement in my code. Setting ‘sym=nil’ in the parameters fixed it. I wonder how long it is going to take me to get used to Ruby’s limited values that test false?
Any way this now works for both symbols and blocks, of course with very limited testing:
def reduce(list, initial=0, sym=nil, &block)
if sym and sym.class == Symbol
list.each{ |i| initial = initial.send(sym,i) }
else
list.each{ |i| initial = block.call(initial, i) }
end
initial
end
irb> evens = reduce(n,[]){ |memo,i| memo << i if i.even?; memo }
=> [2, 4]
irb> evens => [2, 4]

Both of those sites I mentioned have other interesting articles, many that deal with Ruby that sa a beginner I’ve found helpful.
Mauricio, it turns out is a computer science college level instructor in Brasil, I think it was.
Thanks for the challenge, I have learned a lot.
Ciao,
Mike

This is pretty advanced stuff, but let’s see what I can do to help. Let’s start with an example of Ruby’s #reduce method, using the array and arguments in example 1 in your assignment:

[1, 2, 3, 4].reduce(0) { |sum, element| sum + element }

Now, here are the things to know. First, #reduce iterates through each of the values in an array and does whatever the block says to do with them. The block takes two variables. The first one (sum) is the “accumulator.” The accumulator starts equal to whatever value is passed in as an argument to the #reduce method (usually 0, as it is here). It holds the current total. The other variable (element) is assigned to each element, one at a time, one after the other (one per iteration, in other words). So, sum + element adds each element’s value to sum, one at a time.

The return value of the #reduce method is the accumulator variable, in this case sum. So, the code above will return 10, the sum of the four values in the array.

Now, how do you implement this functionality yourself? First, you create a method called reduce. This won’t have the same syntax as the #reduce method (to do that, you would have to “monkey patch” the Array class and override the existing method, and we don’t want to do that), but it will do the same thing. It will have two arguments, the array and the starting value for the accumulator.

You need also to understand up front that any method can take a block argument, without the method having to specify one the way it does with regular arguments. Also, calls to #reduce usually have a block argument, but if not, #reduce returns the input array converted to an Enumerator object.

All right. Let’s start with our method:

def reduce(arr, acc = 0)
  return arr.to_enum unless block_given?
end

So far, so good. If the caller doesn’t provide a block argument, then return an Enumerator instead of raising an error. Also, we’ve put a default of 0 for the accumulator’s start value, since that’s what it usually is. Now for the hard part.

We want to run through each element of the array, and let the block operate on it, just like in the actual #reduce method. To do this, we’ll use while and the yield method:

def reduce(arr, acc = 0)
  return arr.to_enum unless block_given?

  counter = 0

  while counter < arr.size
    acc = yield acc, arr[counter]
    counter += 1
  end

  acc
end

p reduce([1, 2, 3, 4]) { |sum, element| sum + element } # => 10

This is a pretty standard use of a while loop to iterate through the elements of an array, which shouldn’t be unfamiliar to anyone with experience in any language. But that yield might be new, so I’ll explain it a bit.

The Proc object’s yield method “invokes” (calls, sort of) the block argument and passes its arguments to it. If the method with yield in it is called without a block argument, yield will raise an error, unless provisions are made for that by using the #block_given? method to check whether a block argument is available.

The reason for yielding to blocks is that doing so lets you give back control of the program flow to whatever called your method. So, you can write your method to do some basic thing — iterating, for example — and let the caller decide the specifics of how to use the method. As you know, there are several Ruby methods that do some form of iteration and execute a block for each iteration: #each, #select, #reduce, etc.

That’s what we’re doing here. We yield each element to the block one at a time (along with the accumulator, which holds the result of yielding previous elements to the block), and set acc to the value that the block returns (in the case of our block, that’s sum + element, since that’s the last line of code in the block). When we’re all done iterating, we return the final value of acc to the caller. That’s pretty much it.

Now, we can pass in the same block to our reduce method that we pass to the regular #reduce method, and get the same result. In fact, this code can handle any of the blocks that your exercises provide (including the last one where they call it from inside an implementation of the select method), but they do throw you a curve on exercise 2. In this exercise, they’re passing in a range instead of an array — which you can also do with Ruby’s #reduce method. So, we need to add in one more line of code:

def reduce(arr, acc = 0)
  return arr.to_enum unless block_given?

  arr = arr.to_a # <<<<<<< This one
  counter = 0

  while counter < arr.size
    acc = yield acc, arr[counter]
    counter += 1
  end

  acc
end

You can safely call #to_a here, because reduce expects an array, or at least something that can be converted to an array. Also, calling #to_a on an array has no effect, so you’re safe calling it on every input.

There’s also an error in exercise 2; as written, it will return 6 instead of 10. To make it return 10, remove one of the periods from the range definition. The rule is that, for example, 1..4 is one through four inclusive, while 1...4 is one to three, not including four. Two dots includes the right number in the range, three dots excludes it. (The three dots can be useful in things like 0...some_array.size instead of 0..(some_array.size - 1), to create a range of all the indexes in an array.)

Hope this helps!

1 Like

Hey Mike, perhaps my answer will explain some things for you as well. My version doesn’t attempt to use the #reduce shortcuts, since that doesn’t appear to be specified in the exercise. That would be a bit more complicated; in my solution, you’d have to check in the while loop for a shortcut symbol and act accordingly.

FYI, the only values in Ruby that test false are nil and false. Everything else tests true, including ''.

BobRodes,
Thanks for the pointers.
I’ve been struggling to understand how to use yield.
When I replace ‘block.call’ with ‘yield’ in my definition of reduce it performs the same which I hadn’t yet figured out on my own.
My version doesn’t use ‘.to_a’ but seems to work fine with ranges so I suspect Ruby makes that conversion itself.

Regarding Enumerable#reduce the definition I have for 1.9.3 says,
“Combines all elements of enum by applying a binary operation,
specified by a block or a symbol that names a method or operator.”
When I try [1,2,3,4,5].reduce(:even?) I expected to get back [2.4].
Instead I get NoMethodError on reduce([], :even?) and ArguementError on reduce(0, :even?) and reduce(1, :even?).
1.even? is definately a binary method, Am I misunderstanding the docs, are they wrong or have I just not found the right syntax?
I know I can get what I expected with a block but that’s not the point. Understanding reduce is the point.
Thanks for your kind assistance.
Mike

Looking at your second attempt, you’re on the right track. One of the problems that you’re having is not putting a default for initial. So, the calls to your method that don’t have a value for initial are going to error out. So:

def reduce(list, initial = 0)
  list.each do |x|
    yield(initial, x) 
  end
  initial
end

(By the way, you get this nice code layout by indenting everything four spaces.)

This should work, although I still prefer the while loop.

1 Like

Proc#call and Proc#yield are not quite aliases, but they do perform the same — in any circumstance in which you can use either. Proc#yield always works on a block passed in as a block argument, while Proc#call works on a Proc object. When you use &block, you are actually calling the #to_proc method on the block argument, which wraps the block in a Proc object that can then be passed about from method to method if desired. That is something that you can’t do with yield; yield in a method only yields to the block argument that is passed to the method.

Your version doesn’t need to_a not because Ruby makes that conversion itself, but because you’re using #each, which the Range object supports directly (which it has to do if it includes the Enumerable module; any object that includes the Enumerable module is required to provide its own implementation of #each).

I think you are indeed misunderstanding the documentation. A binary operation is a calculation that combines two elements to create a third element. Addition, subtraction, multiplication and division are binary operations. You’re confusing that with the idea that a method that returns true or false is a method with a binary result. Not the same thing. #reduce is intended to work with binary operations as described in the link, and works by accumulating the results of a binary operation performed on all members of an enumerable group one at a time.

Now, if you are attempting to get a subset of an array that fits specified criteria, you’ll want to use #select or one of its derivatives. So, [1,2,3,4,5].select(&:even?) will give you what you want.

Note the ampersand here, which is analogous to the &block ampersand which you’ve already looked at. (You have to have the ampersand except when providing the binary operator to use with #reduce/#inject.) This code is the same as [1, 2, 3, 4, 5].select { |elt| elt.even? } So &:even? calls to_proc on that block and passes the resulting Proc object into the #select method, which then calls the proc. This works for any method that takes a block with a single method call in it.

#reduce works a bit differently, because it can accept a symbol that is a method call as an argument. Methods that support binary operations (:+, :-, etc.) can then be passed directly, so no ampersand.

(You are aware that most of the “operators” in Ruby aren’t really, but are actually methods? For example, this is valid syntax in Ruby: 2.+(3), and is equivalent to 2 + 3.)

Thank you very much!
I am not familiar with .to_enum yet, but i will google that. I am familiar with everything else you used, so thank you, that makes it easier to understand. I didn’t even think of using an iteration (i mean the while loop) but it makes so much sense now!

There is just one more question i have: why do you use yield acc instead of just yield? As i understand yield it takes the whole block, so how come acc is not keeping the code from working? How is it used by yield?

Thanks again :smiley:

Here are the relevant lines of code:

acc = yield acc, arr[counter]

And the call with the block:

reduce([1, 2, 3, 4]) { |sum, element| sum + element } # => 10

Now, you can perhaps write this more clearly with parentheses:

acc = yield(acc, arr[counter])

In Ruby, the parentheses around the argument list are optional, and the convention is to omit them with yield (why, I can’t say; it seems a bit arbitrary really).

Ok. I’m passing two arguments with yield: acc and arr[counter]. When I do this, yield then passes those arguments to the block when it invokes it. (When yield invokes the block, that is.) So, inside the block, sum is equal to what acc was equal to when passing it in with yield, and element is equal to arr[counter] in the yield.

The block code adds the value in element to the value in sum and returns the result, which we then set acc equal to in our method. Therefore, acc accumulates the sum of the values in the array, one at a time.

This behavior is exactly the same as method behavior (blocks don’t behave exactly like methods, but in this they do). This probably looks entirely familiar to you:

def add_two(num1, num2)
  num1 + num2
end

x = add_two(3, 4) 
puts x # => 7

And the block code works the same way. The yield is analogous to the add_two method call, (num1, num2) is analogous to |acc, element| in the block, and the block returns the result of the last line of code the same way that the method does. Does that help?

p.s. You don’t need to be very familiar with Enumerator objects yet. Just know that a lot of methods that typically use blocks return the receiver as an Enumerator when they are called without one. (A “receiver” is an object that calls a method; in this case the array that calls the reduce method.)

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs