概要
自由に扱える集合(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 未満の正の奇数 }
という書き方もできるのです1。
さて、ここで、内包で集合を定義したいと考えます。もちろん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
はデータベースから目的のデータを引っ張ってくる条件を定義する用途で設計されているようです2。なので、任意の集合を定義するためにNSPredicate
を使おうとするのは、ちょっと違うようです。
さらに、Linux版のNSPredicate
はNSUnimplemented()
だらけで使い物になりません3。
これはもう、NSPredicate
を使うのは諦めるしかないでしょう。
自分でpredicateを作るしかない
こうなると自分でpredicateを作っていくしかないでしょう。ただ、ここでpredicateをクラスとして実装するのは、Swiftらしくありません。やはり、Swiftといえばプロトコルでしょう!
ということで、まずはPredicateProtocol
なるプロトコルを作りました。といっても、「predicateは真か偽を返すもの」であればいいので、プロトコロルの定義も簡単です:
public protocol PredicateProtocol {
associatedtype Variable
func evaluate(with argument:Variable) -> Bool
}
Predicateを表すものとしては、Variable
型(associatedtype
)の引き数を取ってBool
型の値を返すevaluate(with:)
さえ実装されていればいいことにします4。
PredicateProtocol
への準拠例
とても単純なものとしては次のようなものになります:
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
を継承するプロトコルの定義は次のように単純です:
public protocol IntensionalSet: SetAlgebra, ConsolidatablePredicate where Element == Variable {}
ソースコードを見てもらえば分かると思いますが、ConsolidatablePredicate
に準拠するように実装すれば、SetAlgebra
が必要とするメソッドのほとんどを、IntensionalSet
のデフォルト実装が提供します。
これでやっと、predicateで定義できる集合(Set)を作る素地ができました。
さっそくIntensionalSet
に準拠する型を作ってみよう
SwiftPredicate
ではIntensionalSet
に準拠する型の一例としてTotallyOrderedSet<Element>
というものを実装してみました5:
public struct TotallyOrderedSet<Element> where Element: Comparable {
private var _ranges: MultipleRanges<Element>
public init(elementsIn ranges:MultipleRanges<Element>) {
self._ranges = ranges
}
}
TotallyOrderedSet<Element>
それ自体はとても単純な構造体です6。
Element
が"countable"かどうかで実装を変えているので冗長なところもありますが、基本的には_ranges
に値が含まれていれば真、含まれていなければ偽とするpredicateとして実装します。and(_:)
やor(_:)
については、MultipleRanges<Element>
にintersection(_:)
やunion(_:)
があるので、それをそのまま使えます。それがSetAlgebra
のintersection(_:)
やunion(_:)
となるのです。具体的な実装はソースコードをご覧ください。
TotallyOrderedSet
の使い方
Swift標準のSet<Element>
を使ってDouble
の集合を作ろうっていうのは無謀ですよね7。でも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 #記法」 ↩
-
NSPredicate.swift in GitHub/apple/swift-corelibs-foundation ↩
-
論理学的には、variableは「変数」ではなく「変項」と言うらしいです。 ↩
-
MultipleRanges<Element>
ってなんだ?というのは別の記事でも紹介したSwiftRangesをご参照ください。 ↩ -
Double
もHashable
に準拠しているのでSet
で使えますが、「1.0以上2.0未満を含む」というようなことはできませんね。 ↩