Haskell の「関数型問題解決法」を Ruby で

すごいHaskellたのしく学ぼう!

第10章。
　
ほぼ忠実な移植。

heathrow_to_London =
  [
    [50, 10, 30],
    [5, 90, 20],
    [40, 2, 25],
    [10, 8, 0]
  ]

make_section = ->(ary) {%i(A B C).zip(ary).to_h}
t_sum = ->(path) {path.sum {_1.values[0]}}

road_step = ->((path_a, path_b), sct) {
  time_a = t_sum.(path_a)
  time_b = t_sum.(path_b)
  foward_time_to_a = time_a + sct[:A]
  foward_time_to_b = time_b + sct[:B]
  cross_time_to_a = time_b + sct[:B] + sct[:C]
  cross_time_to_b = time_a + sct[:A] + sct[:C]
  new_path_to_a = if foward_time_to_a <= cross_time_to_a
                    path_a + [{A: sct[:A]}]
                  else
                    path_b + [{B: sct[:B]}, {C: sct[:C]}]
                  end
  new_path_to_b = if foward_time_to_b <= cross_time_to_b
                    path_b + [{B: sct[:B]}]
                  else
                    path_a + [{A: sct[:A]}, {C: sct[:C]}]
                  end
  [new_path_to_a, new_path_to_b]
}

optimal_path = ->(road_system) {
  best_path_a, best_path_b = road_system.inject([[], []], &road_step)
  t_sum.(best_path_a) <= t_sum.(best_path_b) ? best_path_a : best_path_b
}

path = optimal_path.(heathrow_to_London.map(&make_section))
path_string = path.map {_1.keys[0]}.join
path_time = t_sum.(path)

puts "The best path to take is: " + path_string
puts "Time taken: #{path_time}"

　
結果。

The best path to take is: BCACBBC
Time taken: 75

　
これを見ていると、ここでの関数型プログラミングというのはそれほど特別なものではないな。injectを使っているくらいか。Ruby でも充分に記述できる。ただ、Haskell の強力な型記述で（ある意味では）自然な書き方になっているのはそうかな。

ちなみに、

heathrow_to_London.map(&make_section)
#=>[{:A=>50, :B=>10, :C=>30}, {:A=>5, :B=>90, :C=>20}, {:A=>40, :B=>2, :C=>25}, {:A=>10, :B=>8, :C=>0}]

path
#=>[{:B=>10}, {:C=>30}, {:A=>5}, {:C=>20}, {:B=>2}, {:B=>8}, {:C=>0}]

である。Haskell のSectionを Hash で表している。
　

別解

深さ優先探索（DFS）で総当り。

heathrow_to_London =
  [
    [50, 10, 30],
    [5, 90, 20],
    [40, 2, 25],
    [10, 8, 0]
  ]

result = ["", Float::INFINITY]

go = ->(from, sections, path = "", time = 0) {
  if sections.empty?
    p_re, t_re = result
    result = [path, time] if t_re > time
  else
    (a, b, c), *rest = sections
    case from
    when "A"
      go.("A", rest, path + "A", time + a)
      go.("B", rest, path + "AC", time + a + c)
    when "B"
      go.("A", rest, path + "BC", time + b + c)
      go.("B", rest, path + "B", time + b)
    end
  end
}

go.("A", heathrow_to_London)
go.("B", heathrow_to_London)

puts "The best path to take is: " + result[0]
puts "Time taken: #{result[1]}"