Using `inject`, `unless`, and `next` to determine the minimum value

Question

I have this code:

def test(vertices, distances)
  until vertices.empty?
    nearest_vertex = vertices.inject do |a, b|
      p "a = #{a}: b = #{b}"
      p "distances[a] = #{distances[a]}, distances[b] = #{distances[b]}"
      next b unless distances[a] #next b if distances[a] == true
      next a unless distances[b] #next a if distances[b] == true
      next a if distances[a] < distances[b]
      p "b = #{b}"
      b
    end
    p "nearest_vertex = #{nearest_vertex}"
    vertices.delete nearest_vertex
  end
end

vertices = [1, 2, 3, 4, 5, 6]
distances = {1 => 0, 2 => 3, 3 => 2, 4 => 18, 5 => nil, 6 => 7}
test(vertices, distances)

Which outputs:

"a = 1: b = 2"
"distances[a] = 0, distances[b] = 3"
"a = 1: b = 3"
"distances[a] = 0, distances[b] = 2"
...
"a = 1: b = 6"
"distances[a] = 0, distances[b] = 7"
"nearest_vertex = 1"

Here, b = 6 isn't printed. Is this because next issues a stop iteration command?

"a = 2: b = 3"
"distances[a] = 3, distances[b] = 2"
"b = 3"

Why doesn't the iteration continue to a=2: b=4 here?

"a = 3: b = 4"
"distances[a] = 2, distances[b] = 18"
"a = 3: b = 5"
"distances[a] = 2, distances[b] = "
"a = 3: b = 6"
"distances[a] = 2, distances[b] = 7"
"nearest_vertex = 3"
...

Once a is set to 3, everything works as I thought it should. How does the program know that nearest_vertex is three?

I don't understand the interaction between inject and next in determining how and when to declare a vertex to be the nearest_vertex. How are the distances compared when there is no comparison operator?

Protectionism

I believe you mixed the accumulator and element in block to inject up. According to your comments, you expect it to be |element, accum| whilst it is exactly the opposite: |accum, element|. Try to swap |a, b| to |b, a|. – Phan

"nearest" to what? – Suh

Thanks to the Tin Man for editing my original post. This is my first question posted on StackOverflow and the original format was less than optimal. Nearest is simply comparing "a" to all of the other "b"s and selecting the lowest number. It's a small piece of code taken out of context from an implementation of Dijkstra's algorithm in Ruby. – Protectionism

Answer 1

Let me explain Enumerable#inject in pure Ruby. Note that the following code is NOT the original implementation of Enumerable#inject. For clarity, I will explain it in class Array, and focus on the most basic usage ary.inject(&block):

class Array
  def inject(&block)
    return nil if self.empty?

    enumerator = self.each

    accumulator = enumerator.next

    loop do
      begin
        accumulator = block.call(accumulator, enumerator.next)
      rescue StopIteration
        break
      end
    end

    accumulator
  end
end

You can see that in the loop, the accumulator of previous iteration and the current element of the array is passed to the block's params, and the block's return value is reassigned to the accumulator.

Then what is next x in a block?

You can think of a block as an anonymous function, and the keyword next is its return. It terminates the current block call and makes the block return x (nil if the return value is not explicitly specified).

By the way, break x in a block terminates the method call which takes the block, and makes the method return x. For example:

[1, 2, 3, 4].inject do |acc, n|
   break n if n == 2
   acc + n
end
=> 2

The Array#inject is terminated by the break when n is 2, and that n is returned.

return in a block terminates the method call which calls the method that takes the block. For example:

def foo
  [1, 2, 3].inject do |acc, n|
    return n
  end
  puts 'You will never see this this sentence.'
end

foo
=> 2

And there is no sentence printed, because foo is terminated by return.

Suh

Thank you for taking the time to help me better understand the inject method. Using it in combination with unless was really confusing but I think I understand it much better now. – Protectionism

Answer 2

How inject works

The block passed to inject receives two arguments in each iteration. The first argument (prev_nearest_key here) is an "accumulator" whose value is whatever value was returned by the previous iteration. (For the first iteration it will be the argument given to inject or, inits absence, the first element of the collection—vertices[0] here.) The second argument (key) is the current element of the collection. When iteration is complete, the final value of the accumulator is returned.

When you call next val in a block passed to an iterator, val is immediately returned from the block and the next iteration begins. To demonstrate, here's how it looks with map:

["h", "e", "l", "l", "o"].map do |letter|
  next letter.upcase if "aeoiu".include?(letter)
  letter
end
# => ["h", "E", "l", "l", "O"]

Above, when letter is a vowel, letter.upcase is returned from the block and the next line is never evaluated. When letter isn't a vowel, it's returned from the block unchanged.

Here's a similar example with inject:

["h", "e", "l", "l", "o"].inject do |accum, letter|
  next accum + letter.upcase if "aeoiu".include?(letter)
  accum + letter
end
# => "hEllO"

What's different here? When letter is a vowel, accum + letter.upcase is returned from the block (effectively appending letter.upcase to accum), and the next line is never evaluated. When letter isn't a vowel, accum + letter is returned from the block. In both cases, the value returned from the block becomes accum in the next iteration.

How your code works

Here's your code, but with more intelligible variable names.

nearest_vertex = vertices.inject do |prev_nearest_vertex, current_vertex|
  next current_vertex unless distances[prev_nearest_vertex]
  next prev_nearest_vertex unless distances[current_vertex]
  next prev_nearest_vertex if distances[prev_nearest_vertex] < distances[current_vertex]
  current_vertex
end

I've renamed a, the accumulator, to prev_nearest_vertex, since it's the value returned by the previous iteration, and b to current_vertex.

The first two lines inside the block are just checking to see if distances[prev_nearest_vertex] and distances[current_vertex] are nil. They could (and, perhaps, should) be written like this instead:

next current_vertex if distances[prev_nearest_vertex].nil?
next prev_nearest_vertex if distances[current_vertex].nil?

The first line basically says, "If the previous nearest vertex's distance is nil, then it's not the nearest, so set prev_nearest_vertex to current_vertex in the next iteration." The second line says "If the current vertex's distance is nil, then it's not the nearest, so keep prev_nearest_vertex the same in the next iteration.

And here are the third and fourth lines:

next prev_nearest_vertex if distances[prev_nearest_vertex] < distances[current_vertex]
current_vertex

These could be rewritten like this:

if distances[prev_nearest_vertex] < distances[current_vertex]
  prev_nearest_vertex
else
  current_vertex
end

It just says, "Set prev_nearest_vertex in the next iteration to prev_nearest_vertex if its distance is less; otherwise set it to current_vertex.

This is pretty good code, but you should probably...

Do this instead

Ruby's Enumerable module has a lot of really useful methods, including one called min_by. It evaluates the given block for each element in an Enumerable and returns the element for which the lowest value was returned. To demonstrate, consider this map:

words = ["lorem", "ipsum", "dolor", "sit", "amet"]
words.map {|word| word.size }
# => [5, 5, 5, 3, 4]

This just turns an array of words into an array of their sizes. Now suppose we want to get the word that's the shortest. This is easy with min_by:

words = ["lorem", "ipsum", "dolor", "sit", "amet"]
words.min_by {|word| word.size }
# => "sit"

Instead of returning the words' sizes, this calculates their sizes and then returns the word whose size is the smallest.

This is directly applicable to your code. Again, consider a map operation:

vertices = [1, 2, 3, 4, 5, 6]
distances = { 1 => 0, 2 => 3, 3 => 2, 4 => 18, 5 => nil, 6 => 7 }

vertices.map do |vertex|
  distances[vertex] || Float::INFINITY
end
# => [0, 3, 2, 18, Infinity, 7]

This produces an array of distances corresponding to the elements in vertices, but nil distances are replaced with Float::INFINITY. This is useful because n < Float::INFINITY is true for every number n. As before, we can now replace map with min_by to get the vertex corresponding to the smallest distance:

def test(vertices, distances)
  vertices.min_by {|vertex| distances[vertex] || Float::INFINITY }
end

test(vertices, distances)
# => 1

Underpants