概要

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

はじめに

Swiftには標準でSet<Element>という構造体が用意してあります。

たとえば、

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

なんて使い方をします。

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

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

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

`NSPredicate`はどうですか？

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

そして、Foundationフレームワークには、その名もズバリNSPredicateというクラスが存在します。集合の定義にNSPredicateは使えないでしょうか？

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

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

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

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

自分でpredicateを作るしかない

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

PredicateProtocol.swift

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

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

`PredicateProtocol`への準拠例

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

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を表すインスタンスを作成できます：

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で拡張されているので、andやorといったメソッドを持っています：

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

これで満足？

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

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

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

EquatablePredicate: PredicateProtocolとEquatableを継承するプロトコル
NegatablePredicate: PredicateProtocolを継承するプロトコル。準拠するためにはmutating func negate()という「自身の評価値を反対にする」メソッドを実装する必要がある。
ConsolidatablePredicate: EquatablePredicateとNegatablePredicateを継承するプロトコル。型がSelfのままandやorなどの操作を実行できる。準拠するためにはfunc and(_:Self) -> Selfを実装する必要がある。

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

実際、IntensionalSet(内包表記による集合)というConsolidatablePredicateとSetAlgebraを継承するプロトコルの定義は次のように単純です：

IntensionalSet.swift

public protocol IntensionalSet: SetAlgebra, ConsolidatablePredicate where Element == Variable {}

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

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

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

SwiftPredicateではIntensionalSetに準拠する型の一例としてTotallyOrderedSet<Element>というものを実装してみました⁵：

TotallyOrderedSet.swift

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

TotallyOrderedSet<Element>それ自体はとても単純な構造体です⁶。

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

`TotallyOrderedSet`の使い方

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

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の集合を例にとりましたが、実際に何をしたくてこれを作ったのかは、また別の話…。

参考：「集合 - Wikipedia #記法」 ↩
Qiitaにもいろんな方の記事がありますね。 ↩
NSPredicate.swift in GitHub/apple/swift-corelibs-foundation ↩
論理学的には、variableは「変数」ではなく「変項」と言うらしいです。 ↩
Totally Ordered Setは日本語で全順序集合と呼ばれるものです。 ↩
MultipleRanges<Element>ってなんだ？というのは別の記事でも紹介したSwiftRangesをご参照ください。 ↩
DoubleもHashableに準拠しているのでSetで使えますが、「1.0以上2.0未満を含む」というようなことはできませんね。 ↩