ruby - 如何在 Ruby 中使用递归进行过滤？

Question

如何在 Ruby 中使用递归进行过滤？

假设您有一个对象数组，这些对象具有一个属性，该属性可以具有两个值之一。如果它是第一个值 - 保留对象的第一次出现，如果它是第二个值 - 保留对象的最后一次出现。让我们举个例子:

# 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)

因此，如果它是 :foo，则保留第一次出现并丢弃所有后续(直到到达 :bar)，如果它是 :bar，丢弃除最后一次出现的所有内容(直到到达 :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]

我用迭代来解决这个问题:

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

我在理解如何使用递归执行此操作时遇到问题。特别是，我不知道如何同时跟踪上一个和下一个项目。什么是递归解决方案？

Answer 1

处理 :foo 需要知道前一个元素，而处理 :bar 需要知道下一个；所以在递归的任何给定点，我们必须查看一个三元素窗口，我们可以从中将中间元素添加到我们的结果中。

这是一些模式匹配伪代码(null 表示窗口的那个单元格中没有元素，_ 匹配任何东西；注意匹配案例的顺序很重要) :

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]) ->
  []

这是一个 Ruby 版本:

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

输出:

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>]