SwiftとJavaにおける同一判定/等値判定/比較/順序

Swiftの Equatable と Comparable に詳しくなることを目的とした記事です。せっかくなのでJavaと比べてみます。

SwiftもJavaも強い静的片付けです。 1 は "1" じゃないです。Swiftは参照型と値型があってJavaも参照型とプリミティブ型があります。でもSwiftでは「 String を == で比較しちゃった＞＜」なんて言いません。どこがどう同じで違うのか見ていきます。

確認していく項目は

• 同一判定
• 等値判定
  • nullの扱い
  • ハッシュ値の扱い
  • 他の型との比較
• クラスへの順序付け
  • 等値判定との一貫性
  • nullの扱い
  • 他の型との比較
• コレクションへの順序付け
  • 等値判定との一貫性
  • nullの扱い
  • 他の型との比較
• assertメソッドでの判定

です。

Swift

同一判定

=== 演算子を利用する。 AnyObject 同士の比較で、 Equatable 等を実装しなくても使える。

public func === (lhs: AnyObject?, rhs: AnyObject?) -> Bool {
  switch (lhs, rhs) {
  case let (l?, r?):
    return Bool(Builtin.cmp_eq_RawPointer(
        Builtin.bridgeToRawPointer(Builtin.castToUnknownObject(l)),
        Builtin.bridgeToRawPointer(Builtin.castToUnknownObject(r))
      ))
  case (nil, nil):
    return true
  default:
    return false
  }
}

=== はEquatable.swiftにいる。

等値判定

Equatable を実装した型のみが等値判定を行える。
(error: binary operator '==' cannot be applied)

public protocol Equatable {
  static func == (lhs: Self, rhs: Self) -> Bool
}

Equatable を実装する場合は代替可能性を保つように実装するべきである。互いに等しい2つのインスタンスは、その値を用いるコードで互換性を持つということである。従って、 == は型の可視的な側面を全て考慮するべきである。 Equatable な型はclass identify以外の無価値な側面を公開すべきでないし、公開されているものは全てドキュメントに記すべきである。

Equatable ならば以下の性質を満たさなければならない。

• 反射性( a == a は常にtrue )
• 対称性( a == b ならば b == a )
• 推移性( a == b かつ b == c ならば a == c )

さらに、 a != b は !(a == b) である必要がある。これは標準ライブラリ側で満たしている。

extension Equatable {
  @_transparent
  public static func != (lhs: Self, rhs: Self) -> Bool {
    return !(lhs == rhs)
  }
}

nilの扱い

Optional<T> 自身は Equatable ではないが、 Equatable のものとは別に == がいくつか用意されている。どの == が使われるかはTが Equatable かどうかで定まる。

Tが Equatable であるような Optional<T> とnilを比較した場合は次の == が使われる。

@_inlineable
public func == <T: Equatable>(lhs: T?, rhs: T?) -> Bool {
  switch (lhs, rhs) {
  case let (l?, r?):
    return l == r
  case (nil, nil):
    return true
  default:
    return false
  }
}

Tが Equatable でないような Optional<T> とnilを比較する場合、

@_transparent
public func == <T>(lhs: T?, rhs: _OptionalNilComparisonType) -> Bool {
  switch lhs {
  case .some(_):
    return false
  case .none:
    return true
  }
}

を使用する。 _OptionalNilComparisonType は Equatable でないTでもnilと比較できるようにするもので、true/falseの判定処理そのものには使われない。

Tとnilを比較することもできるがwarningの扱い。
(warning: comparing non-optional value of type to nil always returns false)

ハッシュ値の扱い

Hashable を実装することで Dictionary のキーになれる。
Hashable は Equatable を継承している。

public protocol Hashable : Equatable {
    var hashValue: Int { get }
}

任意の2つのオブジェクトa、bについて、 a == b ならば a.hashValue == b.hashValue である必要がある。 a.hashValue == b.hashValue の時に a == b である必要はない。

他の型との比較

Self により同じ型同士の比較に限定されている。

型への順序付け

型への順序付けは Comparable を実装することにより行う。 Array にはソートメソッドがいくつかあるが、 mutating func sort() / func sorted() -> [Element] を行えるのは Element が Comparable の時のみである。

public protocol Comparable : Equatable {
  static func < (lhs: Self, rhs: Self) -> Bool
  static func <= (lhs: Self, rhs: Self) -> Bool
  static func >= (lhs: Self, rhs: Self) -> Bool
  static func > (lhs: Self, rhs: Self) -> Bool
}

4つのメソッドが定められているが、 Equatable の == と < を実装すれば残りの3つもカバーされるようになっている。

extension Comparable {
  public static func > (lhs: Self, rhs: Self) -> Bool {
    return rhs < lhs
  }
  public static func <= (lhs: Self, rhs: Self) -> Bool {
    return !(rhs < lhs)
  }
  public static func >= (lhs: Self, rhs: Self) -> Bool {
    return !(lhs < rhs)
  }
}

これにより、 a == b / a < b / b < a のどれか1つだけが必ずtrueになる。

また、狭義の全順序が必ず成り立つ。

• 非反射性( a < a は常にfalse)
• 非対称性( a < b ならば !(b < a))
• 推移性( a < b かつ b < c ならば a < c)

実装側の型は、例外として扱われて比較の対象にならないような値を含む場合があるが、そのような値を狭義の全順序の中で扱う必要はない。
FloatingPoint.nan はどのように比較してもfalseを返す。

1.21 > Double.nan        // false
1.21 < Double.nan        // false
1.21 = Double.nan        // false
Double.nan == Double.nan // false

Double.nan.isNaN         // true

位置付けとしてはデフォルトの比較方法の定義で、あとで紹介する areInIncreasingOrder を使えば自由なソートが可能である。

等値判定との一貫性

あり。 Comparable は Equatable を継承している。等号があって初めて不等号の話ができる。

nilの扱い

nilとの比較になることはない。

ちなみに、 Optional への Comparable の実装は可能だが、 Optional where Wrapped: Equatable のような制約付きのものに対してprotocol実装を行うことはできない。
(error: extension with constraints cannot have an inheritance clause)

他の型との比較

Self により同じ型同士の比較に限定されている。

Array への順序付け

(Element, Element) throws -> Bool を用意することでその場に即したソートができる。

mutating func sort(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows

ただし狭義の弱順序が成り立っていなければならない。

• 非反射性( areInIncreasingOrder(a, a) は常にfalse)
• 推移比較可能性( areInIncreasingOrder(a, b) かつ areInIncreasingOrder(b, c) ならば areInIncreasingOrder(a, c))
• 推移不能性(aとbが比較不能でbとcが比較不能ならばaとcも比較不能)

等値判定との一貫性

制限なし。実装に依存する。

nilの扱い

制限なし。実装すれば Array<Optional<T>> のソートも可能。

他の型との比較

(Element, Element) により同じ型同士の比較に限定されている。

assertメソッドでの判定

XCTAssertEqual は Equatable を要求する。

func XCTAssertEqual<T>(
    _ expression1: @autoclosure () throws -> T,
    _ expression2: @autoclosure () throws -> T,
    _ message: @autoclosure () -> String = default,
    file: StaticString = #file,
    line: UInt = #line
) where T : Equatable

型安全の関係上 T? 版が別に存在する。

Java

同一判定

== を用いる。

等値判定

equals メソッドを用いる。
equals メソッド自体はもともとclass Object から生えているものである。しかしその実態は同一判定である。

public boolean equals(Object obj) {
    return (this == obj);
}

継承側はこれをオーバーライドして定める。以下に String の例を示す。

public boolean equals(Object anObject) {
    if (this == anObject) {
        return true;
    }
    if (anObject instanceof String) {
        String anotherString = (String)anObject;
        int n = value.length;
        if (n == anotherString.value.length) {
            char v1[] = value;
            char v2[] = anotherString.value;
            int i = 0;
            while (n-- != 0) {
                if (v1[i] != v2[i])
                    return false;
                i++;
            }
            return true;
        }
    }
    return false;
}

equals メソッドには

• 反射性( x.equals(x) == true )
• 対称性( y.equals(x) == true ならば x.equals(y) == true )
• 推移性( x.equals(y) == true かつ y.equals(z) == true ならば x.equals(z) == true )
• 一貫性( equals 内での比較に使用する情報に変更がない限り結果は一貫して変わらない)

がある。

nullの扱い

null以外のオブジェクトの比較を想定している。相手がnullの場合はfalseになる。

ハッシュ値の扱い

equals メソッドをオーバーライドする際は同じく Object に由来する public int hashCode() もオーバーライドして一緒に面倒を見てやる必要がある。 hashCode には equals に関する次のような規則が定められているからである。

• equals メソッドによる比較で使用する情報に変更がなければ、 hashCode は常に同じ整数を返す
• equals メソッド的に2つのオブジェクトが等しいならば、 hashCode はそれぞれに同じ整数を返す
• equals メソッド的に2つのオブジェクトが異なる場合は、 hashCode は異なる整数を返すほうが望ましい

String では次のように hashCode をオーバーライドしている。

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

他の型との比較

全クラスが Object を継承しているので equals が使える。

クラスへの順序付け

Comparable<? super T> であれば List<T> に対するソートメソッドとして

public static <T extends Comparable<? super T>> void sort(List<T> list)

を使用することができる。
public int compareTo(T o) 実装時には以下が保証されなければならない。

• 全てのxとyについて sgn(x.compareTo(y))== -sgn(y.compareTo(x))
  • 片方が例外スローするならもう片方も例外スローする。
• (x.compareTo(y)>0 && y.compareTo(z)>0) ならば x.compareTo(z)>0
• 全てのzについて x.compareTo(y)==0 が sgn(x.compareTo(z))== sgn(y.compareTo(z)) を意味する

等値判定との一貫性

クラスCの全てのe1とe2について e1.compareTo(e2) == 0 と e1.equals(e2) の結果が一致する時、 equals と一貫性があると言う。
equals との一貫性については必須ではないが、ソートセットやソートマップの動作が保証されなくなるので一貫性を持つことを推奨されている。一貫性がない例として BigDecimal がある。

一貫性がない場合はその旨を明記することが推奨されている。

nullの扱い

nullはどのオブジェクトのインスタンスでもないため例外をスローすべきとされる。

他の型との比較

Comparable<T> は

public interface Comparable<T> {
    public int compareTo(T o);
}

からわかるように、別の型との比較を実装できないこともない。

コレクションへの順序付け

Comparator<T> を用意することで

public static <T> void sort(List<T> list, Comparator<? super T> c)

によるソートを行うことができる。

int compare(T o1, T o2) 実装時には以下が保証されなければならない。

• 全てのxとyについて sgn(compare(x, y))== -sgn(compare(y, x))
  • 片方が例外スローする時のみもう片方も例外スローする。
• ((compare(x, y)>0)&& (compare(y, z)>0)) ならば compare(x, z)>0
• 全てのzについて compare(x, y)==0 が sgn(compare(x, z))==sgn(compare(y, z)) を意味する

等値判定との一貫性

セットSの全てのe1とe2について e1.compareTo(e2) == 0 と e1.equals(e2) の結果が一致する時、 Comparator<T> は equals との一貫性がある。
こちらもソートセットやソートマップの動作が保証されなくなるのでやはり一貫性が推奨される。一貫性がない場合は明記した方がよい。

nullの扱い

オプション次第でnullとの比較が許可される。
Comparator<T> には

public static <T> Comparator<T> nullsLast(Comparator<? super T> comparator)

のようなメソッドが用意されている。

他の型との比較

同じ型同士の比較を想定したものになっている。

@FunctionalInterface
public interface Comparator<T> {
    int compare(T o1, T o2);
    boolean equals(Object obj);
    // 略
}

assertメソッドでの判定

参照型用には Object を取るassertメソッドが用意されている。

static public void assertEquals(String message, Object expected, Object actual)

Object expected がnullかそうでないかで処理が分かれる。nullだった場合はactualがnullかどうかで結果が決まる。nullでない場合は expected.equals(actual) で判定を行う。

一方プリミティブ型用にはそれぞれにメソッドが用意されている。例えば float には

static public void assertEquals(String message, float expected, float actual, float delta)

があって、中では Float の

public static int compare(float f1, float f2) {
    if (f1 < f2)
        return -1;           // Neither val is NaN, thisVal is smaller
    if (f1 > f2)
        return 1;            // Neither val is NaN, thisVal is larger

    // Cannot use floatToRawIntBits because of possibility of NaNs.
    int thisBits    = Float.floatToIntBits(f1);
    int anotherBits = Float.floatToIntBits(f2);

    return (thisBits == anotherBits ?  0 : // Values are equal
            (thisBits < anotherBits ? -1 : // (-0.0, 0.0) or (!NaN, NaN)
             1));                          // (0.0, -0.0) or (NaN, !NaN)
}

を呼び出している。

一目でわかるSwiftとJavaの違い

	Swift	Java
同一判定	===	==
等値判定	==	equals
等値判定に課せられた性質	反射性/対称性/推移性	反射性/対称性/推移性/一貫性
等値判定でのnullとの比較	Optional<T> 型ならtrueになる場合あり	常にfalse
等値である時のハッシュ値の一貫性	Hashable なら必須	必須
等値判定での他の型との比較	不可	可
クラスへの順序付け	Comparable (狭義の全順序)	Comparable<T> (狭義の全順序)
クラスへの順序付けと等値判定の一貫性	常にあり	推奨
クラスへの順序付けでのnullとの比較	不可	例外スロー推奨
クラスへの順序付けでの他の型との比較	不可	可
コレクションへの順序付け	areInIncreasingOrder (狭義の弱順序)	Comparator<T> (狭義の全順序)
コレクションへの順序付けと等値判定の一貫性	言及なし	推奨
コレクションへの順序付けでのnullとの比較	Optional<T> なら可	オプションによっては可
コレクションへの順序付けでの他の型との比較	不可	不可
assertメソッドでの判定	要 Equatable	equals を使用

おまけ

Objective-Cのassertメソッド

SwiftとObjective-Cではassertメソッドが異なる。

改めて並べてみると、

func XCTAssertEqual<T>(_ expression1: @autoclosure () throws -> T, _ expression2: @autoclosure () throws -> T, _ message: @autoclosure () -> String = default, file: StaticString = #file, line: UInt = #line) where T : Equatable
func XCTAssertEqual<T>(_ expression1: @autoclosure () throws -> T?, _ expression2: @autoclosure () throws -> T?, _ message: @autoclosure () -> String = default, file: StaticString = #file, line: UInt = #line) where T : Equatable

XCTAssertEqual(expression1, expression2, ...)
XCTAssertEqualObjects(expression1, expression2, ...)

static public void assertEquals(String message, float expected, float actual, float delta)
static public void assertEquals(String message, Object expected, Object actual)

この点についてはObjCの方がJavaに近い。

順序のルール

狭義の全順序(以下strict total ordering)と狭義の弱順序(以下strict weak ordering)について。れっきとしたどこかの用語である。

何がstrictでtotalでweakかといえば、

• "strict" は非反射性を示す。
• "total" は比較不能を許容しない。そこから、比較不能あり/なしひっくるめたorderingを "partial" と呼ぶ。
• "weak" は "total" より弱く "partial" より強い要求を示す。具体的には推移不能性のこと。

Swiftの Comparable は
『非反射性』
『比較不能を許容しない』( FloatingPoint.nan などは対象外)
よってstrict total orderingである。

一方

areInIncreasingOrder は
『非反射性』
『比較不能を許容する』
『推移不能性』
よってstrict weak orderingである。

たぶん。

ちなみに、Javaの Comparable<T> と Comparator<T> はどちらもクラス説明文でtotal orderingと名乗っていて、メソッド説明で非反射性に触れている。つまりstrict total orderingを想定していると読める。

比較不能については次の項目で。

Let's try

ストーリーは適当。

たかしくんはお兄さんからボールをたくさんもらいました。

struct Ball {
    let diameter: Int
    let color: Color

    enum Color {
        case blue
        case red
        case yellow
    }
}

class Ball {
    int diameter;
    Color color;
    
    public Ball(int diameter, Color color) {
        this.diameter = diameter;
        this.color = color;
    }

    enum Color {
        BLUE, RED, YERROW
    }
}

ボールの大きさや色は様々です。果たして同じボールはあるんだろうか？と思ってしまうほどです。

extension Ball: Equatable {}

/// 反射性、対称性、推移性を満たす
/// 可視的なものは全て織り込み済み
/// (a != b) と !(a == b)の結果が一致する
func ==(lhs: Ball, rhs: Ball) -> Bool {
    return lhs.diameter == rhs.diameter && lhs.color == rhs.color
}

/**
 * 反射性、対称性、推移性、一貫性を満たす
 * hashCodeもオーバーライド済み
 * nullのときはfalseを返す
 */
@Override
public boolean equals(Object anObject) {
    if (this == anObject) {
        return true;
    }
    if (anObject instanceof Ball) {
        Ball anotherBall = (Ball)anObject;
        return this.diameter == anotherBall.diameter && this.color == anotherBall.color;
    }
    return false;
}

/**
 * diameterとcolorに変更がなければ同じ整数を返す
 * `equals` 的に等しいなら同じ整数を返す
 * `equals` 的に異なるなら異なる整数を返す
 */
@Override
public int hashCode() {
    return Objects.hash(this.diameter, this.color);
}

それにしてもたくさんありすぎてどんなボールがあるのかわかりません。今度キャッチボールをするのに使うボールを探そうと、まずは大きさ順に並べることにしました。

let balls: [Ball] = [/* たくさん！ */]

balls.sort {
    return $0.diameter < $1.diameter
}

List<Ball> list = Arrays.asList(/* たくさん！ */);

// nullを許容しないつもり
list.sort((Ball o1, Ball o2) ->
    o1.diameter - o2.diameter
);

たかしくんは比較不能を許容した。色をどう並べるかを決めなかったので同じ大きさのボールの並べ方が定まらない。
(10, 青)と(10, 赤)を考えると、 (10, 青) < (10, 赤)がfalseで(10, 青) > (10, 赤) もfalseである。 < も > もfalseなのだから(10, 青) == (10, 赤)が成立する。つまり同じ大きさの色__違い__のボールは__同じ__。比較不能を許容しない場合なら起きない話である。

この大きさのみに着目した並べ方は

• 非反射性
• 推移比較可能性
• 推移不能性「(10, 青)と(10, 赤)が比較不能で(10, 青)と(10, 黄)が比較不能なら(10, 赤)と(10, 黄)も比較不能」

が成立するので、strict weak orderingである。Swiftの areInIncreasingOrder の要求はstrict weak orderingなので大丈夫。
ところがJavaの Comparator<T> はtotal orderingを名乗っているので合わない。それだけではなく、大きさにしか注目していないということは、同じ大きさのボールに関して e1.compareTo(e2) == 0 と e1.equals(e2) の結果が一致しないことを意味する。つまり Comparator<T> と equals メソッドの間に一貫性がない。

ひととおりボールを並べて満足したたかしくんでしたが、お母さんに怒られたのでお片付けをしなければならなくなりました。せっかくなので、大きさと色をそろえてしまうことにしました。

extension Ball: Comparable {}

/// 非反射性、非対称性、推移性を満たす
func < (lhs: Ball, rhs: Ball) -> Bool {
    if lhs.diameter == rhs.diameter {
        return lhs.color.hashValue < rhs.color.hashValue
    } else {
        return lhs.diameter < rhs.diameter
    }
}

/**
 * 非反射性、非対称性、推移性を満たす
 * `equals` との一貫性あり
 * `o` がnullの時ぬるぽをスロー
 */
@Override
public int compareTo(Ball o) {
    if (this.diameter == o.diameter) {
        return this.color.hashCode() - o.color.hashCode();
    } else{
        return this.diameter - o.diameter;
    }
}

たかしくんは色も見て並べるようになった。これにより equals との一貫性が成立する。もちろん Equatable とも一貫性がある。
色の順番をきちんと決めた結果strict total orderingの要件も満たすようになった。これで Comparable Comparable<T> どちらからの要求も充足される。

参考文献

Java
jdk8/jdk8/jdk: 687fd7c7986d /src/share/classes/
java.lang (Java Platform SE 8)
java.util (Java Platform SE 8)
Assert (JUnit API)

Apple
Swift Standard Library | Apple Developer Documentation
apple/swift: The Swift Programming Language
[swift-evolution] [Draft][Proposal] Formalized Ordering

順序
2004-05-29 - Cry’s Diary
algorithm - cpprefjp C++日本語リファレンス