Проблема с Ruby рекурсивным лямбда-вызовом

Question

У меня есть следующий код, который корректно пересекает все узлы на графике, например так:

seen = {}
dfs = lambda do |node|
  return if seen[node]
  seen[node] = true
  $edges[node].each {|n| dfs.call n}
end
dfs.call 0

Однако я хотел бы написать это так, что, как я понимаю, правильно:

  $edges[node].each &dfs

Однако, когда я делаю это, создается впечатление, что dfs вызывается только для первого элемента списка узлов в $edge[node].Что дает?

Answer 1

Удивительно, но ваша проблема - , а не в рекурсии! Это на самом деле из-за общего набора seen среди всех вызовов в $nodes[node].each &dfs.

Давайте пройдем через операцию: вызов $nodes[node].first не должен иметь никаких проблем, потому что мы знаем, что фрагмент работает для любого отдельного узла. Однако существует проблема: seen не сбрасывается, и вы уже переходите к следующему узлу! Вы уже видели все узлы, поэтому, когда вы попробуете хотя бы один из них в следующем цикле, он сразу же выйдет из процесса из-за условия. То же самое будет происходить с каждым другим вызовом, когда вы перебираете $nodes. Только кажется, что звонки на остальные узлы никогда не происходили!

Чтобы решить вашу проблему, выделите seen для каждого вызова dfs, что мы все еще можем сделать в функциональном программировании:

dfs = lambda do |node|
  seen = []
  sub_dfs = lambda do |sub_node|
    return if seen.include? sub_node
    seen << sub_node
    $edges[sub_node].each &sub_dfs
  end
  sub_dfs.call node
end

$edges[some_node].each &dfs

Теперь seen безопасно изолируется при каждом вызове на dfs.

Answer 2

Еще один способ сделать рекурсивные лямбды:

fac = lambda{|n, &context| n.zero? ? 1 : n * eval("fac.call(#{n-1}) {}",context.binding)}

Но должен вызываться с пустым блоком, хотя

fac.call(2){} = 2
fac.call(3){} = 6
fac.call(4){} = 24

привязка используется для оценки кода вне области действия лямбды