merge_two_sorted_lists_using_linrec.rb

def merge_two_sorted_lists(a, b, &comparator)
  comparator ||= lambda { |x,y| x <=> y }
  linrec(
    :cond   => lambda { |pair| pair.first.empty? || pair.last.empty? },
    :before => lambda do |pair|
      preceding, following = case comparator.call(pair.first.first, pair.last.first)
        when -1; [pair.first, pair.last]
        when 0;  [pair.first, pair.last]
        when 1;  [pair.last, pair.first]
      end
      [ preceding.first, [preceding[1..-1], following] ]
    end, 
    :then => lambda do |pair|
      if pair.first.empty? && pair.last.empty?; []
      elsif pair.first.empty?; pair.last
      else; pair.first
      end
    end,
    :after  => lambda { |trivial_part, recombined| [trivial_part] + recombined }
  ).call([a,b])
end