Why the lambdas hangs in 'each' iterator? Ruby 2.6.5

Question

Ruby 2.6.5

Have a method to interact array of hashes and filter them. User can put array of students and as many filters as he wants. If I use one filter, everything is going fine. But if I put second filter, the program is hangs in irb console and nothing is going on. Memory limit exceeded. What am I doing wrong?

def filter(students, *filters)
  return students if filters.empty?

  result = []
  filters.each do |filter|
    students.each { |student| result << student if filter.call(student) }
    students = result
  end
  result
end

students = [
  { name: 'Thomas Edison', gpa: 3.45 },
  { name: 'Grace Hopper', gpa: 3.99 },
  { name: 'Leonardo DaVinci', gpa: 2.78 }
]

filter_1 = ->(record) { record[:gpa] > 3.0 }
filter_2 = ->(record) { record[:gpa] < 3.9 }

If I will call the method only with filter_1 or filter_2 (filter(students, filter_2)), everything is going fine, but when I put there one more argument (filter(students, filter_1, filter_2)), the programs is hanging.

What I did already

If I will delete only one string (students = result) code will work. And fast return the result:

filter(students, honor_roll, filter_2)
 => [{:name=>"Thomas Edison", :gpa=>3.45}, {:name=>"Grace Hopper", :gpa=>3.99}, {:name=>"Thomas Edison", :gpa=>3.45}, {:name=>"Leonardo DaVinci", :gpa=>2.78}]

But I need exactly implement filters one by one. I tried to modificate arrays of results after implementing each iteration, but there is the same problem. Also I tried to not use students array:


def filter(students, *filters)
  # Write your code here
  return students if filters.empty?

  result = []
  filters.each_with_index do |filter, index|
    array = index.zero? ? students : result
    array.each { |student| result << student if filter.call(student) }
  end
  result
end

But result is the same.

How can I fix this? Thank you so much!

Are you aware that you can just write `students.select(&filter_1).select(&filter_2)`? — Stefan, Dec 06 '19 at 14:02

3limin4t0r · Accepted Answer · 2019-12-06T14:49:59.107

The issue lies in the following lines:

result = []
filters.each do |filter|
  students.each { |student| result << student if filter.call(student) }
  students = result
end

With one filter everything works since students and results are different arrays. However at the end of the first iteration you set students = result which means that the student and result variable refer to the same array.

So what's the problem? The second time you enter the loop you add students to result using result << student (if the filter results to a truthy value). Since both result and students refer to the same array you implicitly add them to the students array, which you are currently iterating.

Let me demonstrates what happens with a simple example:

# Assume we have the students collection: [1] and the filter call will
# always result in a truthy value.
students = [1]
students.each { |student| students << student if true }

Like you can see above by adding elements to the collection you're iterating you end up in an endless loop.

So, what do you need to do to fix this? Without changing your current code too mutch simply moving the result = [] inside the filters.each loop will fix the issue. This will create a brand new array for each iteration.

filters.each do |filter|
  result = []
  students.each { |student| result << student if filter.call(student) }
  students = result
end
students # you can't return `result` any more, since it's not in scope

However, Ruby offers many iteration methods that can help you simplify this whole method. Something like this also does the trick:

def filter(students, *filters)
  students.select do |student|
    filters.all? { |filter| filter.call(student) }
  end
end

Here I use the select iteration method to select the students that match some criteria. I then use the all? iteration method to check if the student matches all filters.

Another one that comes to mind is:

def filter(students, *filters)
  filters.reduce(students) { |students, filter| students.select(&filter) }
end

This uses reduce to reduce the filters collection to a single value (a students collection). While doing this use select to select the students that match the current filter (shrinking the students collection each iteration).

@RuslanValeev If you don't fully understand the `select(&filter)` syntax check out [this](https://stackoverflow.com/questions/1961030/ruby-ampersand-colon-shortcut/1961118) question. — 3limin4t0r, Dec 06 '19 at 14:36

score 2 · Answer 2 · answered Dec 06 '19 at 13:45

The problem is the statement students = result. This makes student point to the same memory location as result -- the are the SAME object from this point forward. So now when you call result << ... that's the same thing as calling students << ..., and therefore the loop never ends because you are constantly appending to the thing you're looping over.

To see this:

students = [1]
result = students
results << 1
students
# => [1,2]

I'd suggest using ruby-core's select (also called filter, in fact) method (or the inverse reject):

results = students
filters.each do |filter|
  results = results.select(&filter)
end

If you don't know & syntax, that's basically equivalent to

results = students
filters.each do |filter|
  results = results.select{|x| filter.call(x)}
end

This way, you're starting with the full list and dump the matching students into a new array for each filter.

Or do them all at once:

students.select{|x| filters.all?{|f| f.call(x) } }

score 1 · Answer 3 · edited Dec 06 '19 at 17:24

The reason it is on a loop is because students and result are referencing the same region of memory when you call students = result, so every time you insert a student element in result the students array increase its size, making the each loop endless, you should use students = result.clone to prevent this. But it's not the only problem, your algorithm is not correct, you should just use this:

def filter(students, *filters)
  return students if filters.empty?
  result = students.clone
  filters.each do |filter|
    result.select! { |student| filter.call(student) }
  end
  result
end

Why the lambdas hangs in 'each' iterator? Ruby 2.6.5

3 Answers3