`Enumerable#uniq?` を実装

raise if ary.dup.uniq! なんて書かれていたら、どんな動作をするのかすぐにはわからない。

動機

配列の要素に重複があるかどうか判定したい。

• Array#uniq! というメソッドがある
  • レシーバーの配列から重複する要素を削除する
  • 重複する要素を削除しなかった場合は nil を返す ＝ 戻り値で「重複の有無」を判定できる
• これをそのまま条件式に使うのは気が引ける
  • 破壊的メソッドのため、事前に配列を複製しないといけない
    • また実際に重複を全排除するのは計算の無駄
  • 「重複の有無」と「戻り値の真偽」の関係がややこしい
  • ⇒ 真偽判定に特化したメソッド #uniq? を作ろう
• さらに言えば Array でなくてもいい
  • ⇒ Enumerable に作ろう
  • ちなみに破壊的でないメソッド #uniq は Enumerable などにもある

実装

#uniq 系は Object#eql? の等価判定に基づいている。ということは重複の検知には Hash のキー部分を使えばいい。 Set なら更に分かりやすいけれども、ライブラリをrequireしなければいけないので却下。

module Enumerable
    def uniq?(&block)
        block ||= :itself.to_proc
        hash = Hash.new
        each do |item|
            key = block.call(item)
            return false if hash.key?(key)
            hash[key] = nil  # register a new key
        end
        true
    end
end

やっていて気付いたが、 BasicObject には #eql? や #hash が無いので、 Hash のキーにできないなど制約がある。組み込みの #uniq 系もエラーを起こすので、上の実装でも BasicObject を無視して Object#itself を使っている。

実験

# `Array#uniq!` と同じ結果になること
chars = [*"a".."z"]
1000.times do
    ary = Array.new(6) { chars.sample }  # 5割前後の確率で重複あり
    expected_result = !ary.dup.uniq!
    raise "wrong implementation!" if ary.uniq? != expected_result
end

なお、今回実装した #uniq? は重複を検知した段階で処理を終えるので、ブロックが副作用を伴う場合は #uniq! と異なる動作になりうる。

ary = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
proc = method(:p).to_proc

p !ary.dup.uniq!(&proc)
p ary.uniq?(&proc)