How to filter with recursion in Ruby?

Question

How to filter with recursion in Ruby?

Say you have an array of objects, that have a property, which can have one of two values. If it's the first value - keep the first occurance of the object, if it is the second value - keep the last occurance of the object. Let's give an example:

# type can be :foo or :bar
MyObject = Struct.new(:id, :type)

a = MyObject.new(1, :foo)
b = MyObject.new(2, :foo)
c = MyObject.new(3, :bar)
d = MyObject.new(4, :bar)
e = MyObject.new(5, :foo)
f = MyObject.new(6, :bar)

So if it is :foo, keep the first occurance and discard all following (until you reach a :bar), if it's a :bar, discard all but the last occurance (until you reach :foo)

# given the initial collection looks like this:
[a, b, c, d, e, f]

# this must be the result after filtering:
[a, d, e, f]

I used iteration to solve this:

initial_collection = [a, b, c, d, e, f]

initial_collection.each_with_object([initial_collection.first]) do |item, filtered_collection|
  if filtered_collection.last.type != item.type
    filtered_collection.push(item)
  elsif item.type == :bar
    filtered_collection[-1] = item
  end
end

I have problems understanding how to do this with recursion. Particularly, I can't wrap my head around how to both keep track of the previous and the next item. What would be a recursive solution?

Answer 1

Processing :foo requires knowing the previous element, while processing :bar requires knowing the next; so at any given point in a recursion, we must look at a three element window from which we might add the middle element to our result.

Here's some pattern-matching pseudocode (null means there is no element in that cell of the window, _ matches anything; note that the order of match cases matters):

f([:foo, :foo, _]) ->
  f(next_window)

f([_, :foo, _]) ->
  [middle_element] + f(next_window)

f([_, :bar, :bar]) ->
  f(next_window)

f([_, :bar, _]) ->
  [middle_element] + f(next_window)

// End of list
f([_, null, null]) ->
  []

Here's a Ruby version:

def f(list, middle_index)
  window = get_window(list, middle_index)

  if window[0,2] == [:foo, :foo]
    f(list, middle_index + 1)

  elsif window[1] == :foo
    [list[middle_index]] +
    f(list, middle_index + 1)

  elsif window[1,2] == [:bar, :bar]
    f(list, middle_index + 1)

  elsif window[1] == :bar
    [list[middle_index]] +
    f(list, middle_index + 1)

  # End of list
  elsif window[1,2] == [nil, nil]
    []
  end
end

def get_window(list, middle_index)
  [maybe_type(list, middle_index - 1),
   maybe_type(list, middle_index),
   maybe_type(list, middle_index + 1)]
end

def maybe_type(list, index)
  if index < 0 or list[index].nil?
    nil
  else
    list[index].type
  end
end

Output:

MyObject = Struct.new(:id, :type)

a = MyObject.new(1, :foo)
b = MyObject.new(2, :foo)
c = MyObject.new(3, :bar)
d = MyObject.new(4, :bar)
e = MyObject.new(5, :foo)
f = MyObject.new(6, :bar)
g = MyObject.new(7, :bar)

arr = [a,b,c,d,e,f,g]

puts f(arr, 0).inspect
# [#<struct MyObject id=1, type=:foo>,
#  #<struct MyObject id=4, type=:bar>,
#  #<struct MyObject id=5, type=:foo>,
#  #<struct MyObject id=7, type=:bar>]

Answer 2

The recursion must receive an extra argument to keep track of the current state, we use type for it.

def recursive_filter(objects, type=nil)
  return [] if objects.empty?  # Stop condition
  first = objects.shift

  if first.type == type
    recursive_filter(objects, first.type)
  else
    [first] + recursive_filter(objects, first.type)
  end
end