Convert callback into iterator with continuations

convert_callback_into_iterator.rb

#!/usr/bin/env ruby

require 'pp'
require 'continuation'

def map_tree(tree, &proc)
  if tree.is_a? Array
    tree.map { |node| map_tree(node, &proc) }
  else
    proc[tree]
  end
end

def make_iterator(tree)
  -> flow {
    map_tree(tree) { |leaf|
      flow = callcc { |k| flow[leaf, k] }
    }
    flow[false, false]
  }
end

def next_step(iterator)
  callcc { |k| iterator[k] }
end

def fold_trees(acc, iterator_a, iterator_b, &proc)
  leaf_a, next_iterator_a = next_step(iterator_a)
  leaf_b, next_iterator_b = next_step(iterator_b)
  if next_iterator_a && next_iterator_b
    next_acc = proc[acc, leaf_a, leaf_b]
    fold_trees(next_acc, next_iterator_a, next_iterator_b, &proc)
  else
    acc
  end
end

def trees_prefix(tree_a, tree_b)
  callcc do |return_cont|
    fold_trees([],
      make_iterator(tree_a),
      make_iterator(tree_b)
    ) do |acc, leaf_a, leaf_b|
      if leaf_a == leaf_b
        acc << leaf_a
      else
        return_cont[acc]
      end
    end
  end
end

tree1 = [1, 2, 3, 4, [3]]
tree2 = [[1], [2, 3, 4], 7, 19, 21, 22, 111]

puts "map_tree(tree1)"
map_tree(tree1) { |t| puts t }

puts "map_tree(tree2)"
map_tree(tree2) { |t| puts t }

puts "trees_prefix(tree1, tree2)"
pp trees_prefix(tree1, tree2)

convert_callback_into_iterator_with_fibers.rb

#!/usr/bin/env ruby

require 'pp'
require 'fiber'

def map_tree(tree, &proc)
  if tree.is_a? Array
    tree.map { |node| map_tree(node, &proc) }
  else
    proc[tree]
  end
end

def make_iterator(tree)
  Fiber.new do
    map_tree(tree) do |leaf|
      Fiber.yield leaf, Fiber.current
    end
    Fiber.yield(false, false)
  end
end

def next_step(iterator)
  iterator.resume
end

def fold_trees(acc, iterator_a, iterator_b, &proc)
  leaf_a, next_iterator_a = next_step(iterator_a)
  leaf_b, next_iterator_b = next_step(iterator_b)
  if next_iterator_a && next_iterator_b
    next_acc = proc[acc, leaf_a, leaf_b]
    fold_trees(next_acc, next_iterator_a, next_iterator_b, &proc)
  else
    acc
  end
end

def trees_prefix(tree_a, tree_b)
  catch(:result) do
    fold_trees([],
      make_iterator(tree_a),
      make_iterator(tree_b)
    ) do |acc, leaf_a, leaf_b|
      if leaf_a == leaf_b
        acc << leaf_a
      else
        throw :result, acc
      end
    end
  end
end

tree1 = [1, 2, 3, 4, [3]]
tree2 = [[1], [2, 3, 4], 7, 19, 21, 22, 111]

puts "map_tree(tree1)"
map_tree(tree1) { |t| puts t }

puts "map_tree(tree2)"
map_tree(tree2) { |t| puts t }

puts "trees_prefix(tree1, tree2)"
pp trees_prefix(tree1, tree2)