[Swift] もっと自由なSetが欲しい。

# 概要

自由に扱える集合(Set)が欲しいと思ったので、作ったよ。
[SwiftPredicate](https://github.com/YOCKOW/SwiftPredicate)という名前のパッケージにしてGitHubで公開したよ。


# はじめに

Swiftには標準で[`Set<Element>`](https://developer.apple.com/documentation/swift/set)という構造体が用意してあります。

たとえば、

```Swift
let 一桁の奇数: Set<UInt> = [1, 3, 5, 7, 9]
```

なんて使い方をします。

数学的には、一桁の奇数を表す集合をXとすると、`X := {1, 3, 5, 7, 9}`なんて書き方をします。このように、集合に含まれる元(要素; element)を列挙する記法を*外延*による表記なんていうようです。Swiftの`Set<Element>`は、外延表記で集合を定義するための構造体と考えればいいでしょう。
一方、集合には*内包*による表記なんてものも存在して、Xについていえば、`X := { x | x は 10 未満の正の奇数 }`という書き方もできるのです[^intension]。

[^intension]: 参考：「[集合 - Wikipedia #記法](https://ja.wikipedia.org/wiki/%E9%9B%86%E5%90%88#%E8%A8%98%E6%B3%95)」

さて、ここで、内包で集合を定義したいと考えます。もちろん**Swiftで**。次のような書き方ができるといいのですが…。

```Swift
let 内包表記による一桁の奇数 = SomeSet<UInt>({ $0 < 10 && $0 % 2 != 0})
```


# `NSPredicate`はどうですか？

数学用語に[predicate](https://en.wikipedia.org/wiki/Predicate_(mathematical_logic))という用語があります。Predicateとは、プログラミング的に言えば、「真か偽かを返す関数」といったところでしょうか。そして、P(x)というpredicateがあったとして、「P(x)が真を返すようなxを元とする集合」を`{ x | P(x) }`と書きます。
要するに、内包表記による集合の定義は「predicateによる集合の定義」と言い換えることもできるはずです。

そして、`Foundation`フレームワークには、その名もズバリ[`NSPredicate`](https://developer.apple.com/documentation/foundation/nspredicate)というクラスが存在します。集合の定義に`NSPredicate`は使えないでしょうか？

結論から言うと、ちょっと難しい…です。

`NSPredicate`のドキュメントを読んでもらうと分かるかと思いますが、`NSPredicate`はデータベースから目的のデータを引っ張ってくる条件を定義する用途で設計されているようです[^nspredicate_in_qiita]。なので、任意の集合を定義するために`NSPredicate`を使おうとするのは、ちょっと違うようです。

[^nspredicate_in_qiita]: Qiitaにも[いろんな方の記事](https://qiita.com/search?q=NSPredicate)がありますね。

さらに、Linux版の`NSPredicate`は`NSUnimplemented()`だらけで使い物になりません[^nspredicate_on_linux]。

[^nspredicate_on_linux]: [NSPredicate.swift in GitHub/apple/swift-corelibs-foundation](https://github.com/apple/swift-corelibs-foundation/blob/master/Foundation/NSPredicate.swift)

これはもう、`NSPredicate`を使うのは諦めるしかないでしょう。


# 自分でpredicateを作るしかない

こうなると自分でpredicateを作っていくしかないでしょう。ただ、ここでpredicateをクラスとして実装するのは、Swiftらしくありません。やはり、Swiftといえばプロトコルでしょう！
ということで、まずは`PredicateProtocol`なるプロトコルを作りました。といっても、「predicateは真か偽を返すもの」であればいいので、プロトコロルの定義も簡単です：

```Swift:PredicateProtocol.swift
public protocol PredicateProtocol {
  associatedtype Variable
  func evaluate(with argument:Variable) -> Bool
}
```


Predicateを表すものとしては、`Variable`型(`associatedtype`)の引き数を取って`Bool`型の値を返す`evaluate(with:)`さえ実装されていればいいことにします[^variable]。

[^variable]: 論理学的には、variableは「変数」ではなく「変項」と言うらしいです。


## `PredicateProtocol`への準拠例

とても単純なものとしては次のようなものになります：

```Swift:SimplePredicate.swift
struct SimplePredicate<Variable>: PredicateProtocol {
  var _predicate: (Variable) -> Bool
  
  init(_ predicate:@escaping (Variable) -> Bool) {
    self._predicate = predicate
  }
  
  func evaluate(with argument: Variable) -> Bool {
    return self._predicate(argument)
  }
}
```

これで、クロージャを使ってpredicateを表すインスタンスを作成できます：

```Swift
let 一桁の自然数 = SimplePredicate<UInt>({ $0 < 10 })
let 奇数 = SimplePredicate<UInt>({ $0 % 2 != 0 })

一桁の自然数.evaluate(with:6) // -> true
一桁の自然数.evaluate(with:17) // -> false
奇数.evaluate(with:6) // -> false
奇数.evaluate(with:17) // -> true
```

さらに、`PredicateProtocol`は[PredicateBinaryOperation.swift](https://github.com/YOCKOW/SwiftPredicate/blob/master/Sources/Predicate/PredicateBinaryOperation.swift)で拡張されているので、`and`や`or`といったメソッドを持っています：

```Swift
let predicateによる一桁の奇数 = 一桁の自然数.and(奇数)
predicateによる一桁の奇数.evaluate(with:6) // -> false
predicateによる一桁の奇数.evaluate(with:7) // -> true
predicateによる一桁の奇数.evaluate(with:17) // -> false
```


## これで満足？

`PredicateProtocol`に準拠した型を定義することで「内包表記によって定義された集合」を表すことはできそうです。しかし、集合といえばいろいろな操作(和集合とか差集合とか補集合とか)がついてくるのが常でしょう。実際、Swiftでは[`SetAlgebra`](https://developer.apple.com/documentation/swift/setalgebra)というプロトコルが用意されていて、集合(Set)に関するいろいろな操作が規定されています。当然、`Set<Element>`は`SetAlgebra`に準拠しています。一方で、`PredicateProtocol`だけで`SetAlgebra`に準拠させることはできそうにありません。


## `SetAlgebra`に準拠するpredicateを作ろう

というわけで、`SetAlgebra`に準拠するプロトコルを作ることができるよう`PredicateProtocol`を継承するプロトコルを作っていきましょう。ここでは簡単に紹介するに留めます：

* [`EquatablePredicate`](https://github.com/YOCKOW/SwiftPredicate/blob/master/Sources/Predicate/Protocols/EquatablePredicate.swift): `PredicateProtocol`と`Equatable`を継承するプロトコル
* [`NegatablePredicate`](https://github.com/YOCKOW/SwiftPredicate/blob/master/Sources/Predicate/Protocols/NegatablePredicate.swift): `PredicateProtocol`を継承するプロトコル。準拠するためには`mutating func negate()`という「自身の評価値を反対にする」メソッドを実装する必要がある。
* [`ConsolidatablePredicate`](https://github.com/YOCKOW/SwiftPredicate/blob/master/Sources/Predicate/Protocols/ConsolidatablePredicate.swift): `EquatablePredicate`と`NegatablePredicate`を継承するプロトコル。型が`Self`のまま`and`や`or`などの操作を実行できる。準拠するためには`func and(_:Self) -> Self`を実装する必要がある。

この最後の`ConsolidatablePredicate`がとても重要になってきます。`and`や`or`などの操作を実行して返ってくる型が自身と同じであれば、`SetAlgebra`における`intersection(_:)`や`union(_:)`にそのまま流用できるからです。

実際、[`IntensionalSet`(内包表記による集合)](https://github.com/YOCKOW/SwiftPredicate/blob/master/Sources/Predicate/Protocols/IntensionalSet.swift)という`ConsolidatablePredicate`と`SetAlgebra`を継承するプロトコルの定義は次のように単純です：

```Swift:IntensionalSet.swift
public protocol IntensionalSet: SetAlgebra, ConsolidatablePredicate where Element == Variable {}
```

ソースコードを見てもらえば分かると思いますが、`ConsolidatablePredicate`に準拠するように実装すれば、`SetAlgebra`が必要とするメソッドのほとんどを、`IntensionalSet`のデフォルト実装が提供します。

これでやっと、predicateで定義できる集合(Set)を作る素地ができました。


# さっそく`IntensionalSet`に準拠する型を作ってみよう

`SwiftPredicate`では`IntensionalSet`に準拠する型の一例として[`TotallyOrderedSet<Element>`](https://github.com/YOCKOW/SwiftPredicate/blob/master/Sources/Predicate/TotallyOrderedSet.swift)というものを実装してみました[^totally_ordered_set]：

```Swift:TotallyOrderedSet.swift
public struct TotallyOrderedSet<Element> where Element: Comparable {
  private var _ranges: MultipleRanges<Element>
  public init(elementsIn ranges:MultipleRanges<Element>) {
    self._ranges = ranges
  }
}
```

[^totally_ordered_set]: Totally Ordered Setは日本語で[全順序集合](https://ja.wikipedia.org/wiki/%E5%85%A8%E9%A0%86%E5%BA%8F)と呼ばれるものです。

`TotallyOrderedSet<Element>`それ自体はとても単純な構造体です[^multiple_ranges]。

[^multiple_ranges]: `MultipleRanges<Element>`ってなんだ？というのは[別の記事](https://qiita.com/YOCKOW/items/d670a347757d4bc0e812)でも紹介した[SwiftRanges](https://github.com/YOCKOW/SwiftRanges)をご参照ください。

`Element`が"countable"かどうかで実装を変えているので冗長なところもありますが、基本的には`_ranges`に値が含まれていれば真、含まれていなければ偽とするpredicateとして実装します。`and(_:)`や`or(_:)`については、`MultipleRanges<Element>`に`intersection(_:)`や`union(_:)`があるので、それをそのまま使えます。それが`SetAlgebra`の`intersection(_:)`や`union(_:)`となるのです。具体的な実装はソースコードをご覧ください。


## `TotallyOrderedSet`の使い方

Swift標準の`Set<Element>`を使って`Double`の集合を作ろうっていうのは無謀ですよね[^double]。でも`TotallyOrderedSet`ならできちゃうんです。

[^double]: `Double`も`Hashable`に準拠しているので`Set`で使えますが、「1.0以上2.0未満を含む」というようなことはできませんね。

```Swift
var set = TotallyOrderedSet<Double>(elementsIn:0.0..<5.0)
set.contains(Double.pi) // -> true

set.invert() // 反転
set.contains(Double.pi) // -> false
set.contains(Double.infinity) // -> true

set.insert(elementsIn:1.0<.<2.0)
set.contains(2.0.squareRoot()) // -> true
```

ね、簡単でしょう？


# おわりに

`Comparable`だけど`Hashable`じゃない型の集合を作りたいと思っていて、どうせなら抽象的に扱えるようにプロトコルをまず実装しようとしてできたのが、今回の`SwiftPredicate`です。
この記事では`Double`の集合を例にとりましたが、実際に何をしたくてこれを作ったのかは、また[別の話](https://qiita.com/YOCKOW/items/8008364a4d86d195e8d4)…。