Ruby: Enumerableをreduceで徹底理解する#3 ソートとステート（翻訳）

参考: Enumerable#inject (Ruby 3.0.0 リファレンスマニュアル) -- reduceはinjectのエイリアスです

Ruby: Enumerableをreduceで徹底理解する#3 ソートとステート（翻訳）

Enumerable系関数をreduceで理解するうえで、もう少し説明の必要な関数がいくつかあります。最初の記事でハッシュやオブジェクトをreduceで理解したときのことを思い出して、ここでもやってみることにしましょう。

ソート

ここが楽しい部分です。Rubyはデフォルトでクイックソートアルゴリズムの変種を用いているので、私たちのコンパレータ（比較器）関数の理念に忠実に進めることにします。

sortとsort_byはキーが少ない場合の速度が約10倍と著しく異なる点にご注意ください。sort_byが生成するタプルのセットは、コンパレータソートではなく単項関数ソートに使われます（Ruby 2.4.2 sort_by）

手始めにシンプルなクイックソートをやってみましょう。

def sort(list)
  return [] if list.empty?

  head, *tail = list

  left  = tail.select { |i| i < head }
  right = tail.select { |i| i >= head }

  [*sort(left), head, *sort(right)]
end

sort([5,4,2,3,1])
# => [1, 2, 3, 4, 5]

原注: Rubyの*記号は、リストのコンテキストではsplat演算子になります。詳しくは以下の記事をどうぞ。
参考: Using splats to build up and tear apart arrays in Ruby

このクイックソートの原理は、要素リストの先頭を「ピボット」として選び、その要素より小さい要素のリストと、その要素と等しいかより大きい要素のリストに分割（partitioning）します。リストを2つに分割したら、それぞれについて同様にリストの分割を再帰的に繰り返すことで最終的にソート済みのリストを得られます。

しかし上の実装はどうも変な気がします。関数をコンパレータとして使っていませんし、再帰を何の工夫もなく使っているに過ぎません。もう少しマシなものにするにはどこから手を付けたらよいでしょうか？

最初に手を付けるのは、先ほども書いた「分割」の部分です。

def sort(list, &fn)
  fn ||= -> (a, b) { a <=> b }

  return [] if list.empty?

  head = list[0]

  left, center, right = list.reduce(
    Array.new(3) { [] }
  ) { |state, i|
    state[fn[i, head] + 1] << i
    state
  }

  [*sort(left, &fn), *center, *sort(right, &fn)]
end

sort([5,4,2,3,1])
# => [1, 2, 3, 4, 5]

原注: fn ||= -> {}を使う理由ですか？Rubyはデフォルトのブロックパラメータをあまり好まないので、少々裏技が必要になります。

ここにはいくつかの概念が導入されていますが、おそらく見慣れない方もいるかもしれません。最初の宇宙船演算子<=>は、コンパレータとして動作します。

参考: Ruby Spaceship <=> Operator

次はleft, center, rightに分けて代入していることです。これは、先頭の要素より小さいか、等しいか、大きいかを示す値を返す宇宙船演算子<=>と連動します。先頭の要素はコンパレータ関数のピボットとして使われます。<=>が-1から始まるので、きれいに分解できるように+1して0にします。

続いてArrayでブロックを作成しています。これは、要素が3つあるArrayがここで1つ欲しかったというだけのことです。

Array.new(3) { [] }

上述のleftを要素0、centerを要素1、rightを要素2にそれぞれ分割しています。それからleftの要素とrightの要素をソートして、splat演算子で配列の入れ子をflatten的に取り除きます。

単項ソート

上述のようにアリティ（arity: 引数の個数）が1のsort_by関数は低速です。しかしここにちょっぴり裏技を加えてみたらどうでしょう？Enumerableはreduceで実装できるのですから、ここでsort_byを自作してソートしてみましょう。

def sort_by(list, &fn)
  sort(list) { |a, b| fn[a] <=> fn[b] }
end

sort_by(%w[foo foobar baz bazzy]) { |w| w.length }
# => ["foo", "baz", "bazzy", "foobar"]

sort_by(%w[foo foobar baz bazzy]) { |w| -w.length }
# => ["foobar", "bazzy", "foo", "baz"]

できました！

minとmax

今度はソートを実装したメソッドをいくつか見て結果を調べましょう。まともに書くとコード量が増えるので、上で定義したsortやsort_byを流用することにします。

minとfirst

minには、カウンタやコンパレータと同様にいくつの記法かあります。

def min(list, n = 1, &fn)
  fn ||= -> (a, b) { a <=> b }

  sorted = sort(list, &fn)
  (n > 1) ? sorted.first(n) : sorted.first
end

min([5,6,1, -10])
# => -10

min([5,6,1, -10], 2)
# => [-10, 1]

ケース1は、1個の最小値が欲しいだけの場合です。ケース2は値の配列を得られます。それではケース1にちょっぴり小技を効かせてみましょう。

def first(list, n = nil)
  return list[0] unless n

  list.reduce([]) { |a,i|
    break a if a.size == n
    a.push(i)
  }
end

first([1,2,3])
# => 1

first([1,2,3], 2)
# => [1, 2]

first([1,2,3], 4)
# => [1, 2, 3]

min_byは基本的にsort_byと同じ概念です。

def min_by(list, n = 1, &fn)
  min(list, n) { |a, b| fn[a] <=> fn[b] }
end

min_by([5,6,1, -10]) { |a| a**2 }
# => 1

min_by([5,6,1, -10], 2) { |a| a**2 }
# => [1, 5]

maxとlast

maxは、minと逆である以外は同じです。

def max(list, n = 1, &fn)
  fn ||= -> (a, b) { a <=> b }

  sorted = sort(list, &fn)
  n > 1 ? sorted.last(n) : sorted.last
end

max([5,6,1, -10])
# => 6

max([5,6,1, -10], 2)
# => [5, 6]

最後のlastですが、これは少しばかりややこしい面があります。lastはRubyのうれしい機能ですが、関数型プログラミングとして完全ではないので、ここにも小技を効かせてみましょう。

def last(list, n = nil)
  return list[-1] unless n

  lasts = []

  list.reduce(0) { |i, _|
    break lasts if lasts.size == n
    lasts.push(list[-1 - i])
    i + 1
  }

  lasts
end

同じ要領でmax_byも以下のようにしてみます。

def max_by(list, n = 1, &fn)
  max(list, n) { |a, b| fn[a] <=> fn[b] }
end

max_by([5,6,1, -10]) { |a| a**2 }
# => -10

max_by([5,6,1, -10], 2) { |a| a**2 }
# => [6, -10]

minmaxとstate

しかし、使いこなしが簡単とは言えない関数もいくつかあります。そのような関数で値をキャプチャしたいときは、コンテキストを多少渡してやる必要があります。

もちろん、外部の配列を使ってやる方法もあるのですが、それではコードが汚くなってしまいます。

手始めにハッシュでやってみましょう。

def minmax(list, &fn)
  fn ||= -> (a, b) { a <=> b }

  head, *tail = list
  result = tail.reduce({
    min: head,
    max: head
  }) { |state, i|
    min = fn[state[:min], i] > 0 ? i : state[:min]
    max = fn[state[:max], i] < 0 ? i : state[:max]

    {min: min, max: max}
  }

  [result[:min], result[:max]]
end

minmax([5,6,1, -10])
# => [-10, 6]

以前私が、reduceでは「何をreduceするか」をそれほど重要視しないと申し上げたことを思い出してみましょう。ではオブジェクトをreduceするとどうなるでしょうか？

MinMax = Struct.new(:min, :max)

def minmax(list, &fn)
  fn ||= -> (a, b) { a <=> b }

  head, *tail = list
  result = tail.reduce(MinMax.new(head, head)) { |state, i|
    min = fn[state.min, i] > 0 ? i : state.min
    max = fn[state.max, i] < 0 ? i : state.max

    MinMax.new(min, max)
  }

  [result.min, result.max]
end

minmax([5,6,1, -10])
# => [-10, 6]

def minmax_by(list, &fn)
  minmax(list) { |a, b| fn[a] <=> fn[b] }
end

minmax_by([5,6,1, -10]) { |a| a**2 }
# => [1, -10]

もちろん上で配列を使ってもよいのですが、このように考えることで可能性が大きく広がるところをぜひ想像してみてください。私は今回アキュムレータ（accumlator）と呼ばずにstateと呼んでいることにお気づきでしょうか？それには理由があるのですが、詳しく説明するにはもう少し準備が必要です。

まとめ:「もし可能だったら」

今回の記事をまとめる代わりに、本シリーズの最初の記事のまとめをおさらいすることにします。

「何もない（nothing）」または「何かがある（something）」というものを定義できたらどうなるでしょうか？

もしそれが可能であれば、map_selectや、その他のさまざまな操作の組み合わせの概念にどんな影響を与えるでしょうか？

関連記事

Ruby: Enumerableをreduceで徹底理解する#1 基本編（翻訳）

Ruby: Enumerableを`reduce`で徹底理解する#2 — No-OpとBoolean（翻訳）