Swiftのstruct・enumと代数学

Swift の struct・enum と代数学 part1 (#4 Algebraic Data Types) iOS アプリ開発のためのFunctional Architecture情報共有会2

今回のテーマについて なぜこのテーマ？ TCA で使われている Case Paths について学びたかった Case Paths を学ぼうとしたら #51 Structs Enums を 先に読むべきとお勧めされた #51 Structs Enums を読もうとしたら、以下を先に読むと 良いとお勧めされた #4 Algebraic Data Types #9 Algebraic Data Types: Exponents #19 Algebraic Data Types: Generics and Recursion 2

そこで今回は三つのうちの⼀つをまとめます #4 Algebraic Data Types 代数データ型 #9 Algebraic Data Types: Exponents 代数データ型：指数 #19 Algebraic Data Types: Generics and Recursion 代数データ型： Generics と再帰 ※ ⾃分の解釈も多分に含まれます 3

代数学とこのテーマの概要 代数学（引⽤：物理のかぎしっぽ） 代数式：有限個の係数や未知数を「+, -, x, ÷, √」の五つの演算 だけを組み合わせて作った式（今回はこちらのみ） 未知数が代数式の形で表される⽅程式を代数⽅程式と呼ぶ a0 xn + a1 xn−1 + ... + an−1 x + an = 0 テーマの概要 struct と enum を代数学を使って⾒ていこう（ざっくり） 4

早速 struct から⾒ていきます struct Pair<A, B> { let first: A let second: B } ↓4 つのパターンを作ることができる Pair<Bool, Pair<Bool, Pair<Bool, Pair<Bool, Bool>(first: Bool>(first: Bool>(first: Bool>(first: true, second: true) true, second: false) false, second: true) false, second: false) 5

オリジナルの enum を作って適⽤してみる 全部で六つのパターンが出来上がる オリジナルの // enum enum Three { case one case two case three } Pair<Bool, Pair<Bool, Pair<Bool, Pair<Bool, Pair<Bool, Pair<Bool, Three>(first: Three>(first: Three>(first: Three>(first: Three>(first: Three>(first: true, second: .one) true, second: .two) true, second: .three) false, second: .one) false, second: .two) false, second: .three) 6

Void についても⾒ていきます は奇妙な型である ⼀つ⽬の理由：型と値を同じように参照できる Void は型で、 () は Void の値 Void _: Void = Void() _: Void = () _: () = () 7

Void が奇妙である⼆つ⽬の理由：値が⼀つ の値は⼀つ（「()」）しかない () には Void の中にあるものを表す値があるだけで、 () は何もできない 返り値を持たない関数が、明⽰的に指定されていなくても こっそり Void を返すのはこのため Void func foo(_ x: Int) /* -> Void */ { // return () } 8

Void ↓ を先ほどの Pair に適⽤してみる は⼆つのパターンしか存在しない Pair<Bool, Void>(first: true, second: ()) Pair<Bool, Void>(first: false, second: ()) ↓ は⼀つのパターンだけ！ Pair<Void, Void>(first: (), second: ()) 9

もう⼀つの奇妙な型 Never enum Never {} は case を持たない enum つまり値を持たない型 Never _: Never = ??? もちろん ↑ のようなことをしてコンパイルすることはできない 10

Never を Pair に適⽤すると？ Pair<Bool, Never>(first: true, second: ???) に⼊れられるものは何もない Never もコンパイラによって特別な扱いを受けている Never を返す関数は何も返さない関数として知られている 例えば fatalError は Never を返す コンパイラは fatalError を実⾏後のコードの全ての⾏と分岐は 無意味になることを知っている それを使ってコードの網羅性を証明することもできる ↑ ??? 11

Pair<A, B> // // // // // ↓A // // // // // Pair<Bool, Pair<Bool, Pair<Bool, Pair<Void, Pair<Bool, の値の数の関係はどうなっている？ Bool> Three> Void> Void> Never> = = = = = 4 6 2 1 0 の値の数と B の値の数の乗算で表されている！ Pair<Bool, Pair<Bool, Pair<Bool, Pair<Void, Pair<Bool, Bool> Three> Void> Void> Never> = = = = = 4 6 2 1 0 = = = = = 2 2 2 1 2 * * * * * 2 3 1 1 0 12

これは Pair 以外の構造体にも当てはまる enum Theme { case light case dark } enum State { case highlighted case normal case selected } struct Component { let enabled: Bool // 2 let state: State // 3 let theme: Theme // 2 } // Bool * State * Theme = 2 * 3 * 2 = 12 13

型の名前を全て⼀掃する フィールドにどのようなデータが格納されているかだけに焦点を 当てる // // // // // Pair<A, B> Pair<Bool, Pair<Bool, Pair<Bool, Pair<Bool, Bool> Three> Void> Never> = = = = = A * B Bool * Bool * Bool * Bool * Bool Three Void Never ざっくり、 Pair<A, B> は A と B の要素数の乗算であるという⾵に 直感的に読むというイメージ あくまで直感の助けになるので、このように読もうという話 14

値が有限でないものは？ String には無限⼤の数が存在するが、 2 x ∞ と考えて良い // Pair<Bool, String> = Bool * String ↓ も無限⼤の要素数同⼠を掛け合わせていると考えることができる // String * [Int] // [String] * [[Int]] 15

他の型も⼀掃して読んでみる // Never = 0 // Void = 1 // Bool = 2 は Void, Never, Bool の名前を⼀掃して、型の中に含まれる値の数 だけを表現している つまり今は特定の型について考えているのではなく、抽象的な 代数的実体を考えているだけ Swift を代数的に捉えることが可能になった ↑ 16

enum はどうか？ enum Either<A, B> { case left(A) case right(B) } ↓ Bool, Bool Either<Bool, Either<Bool, Either<Bool, Either<Bool, なら（2 + 2）パターン Bool>.left(true) Bool>.left(false) Bool>.right(true) Bool>.right(false) 17

enum はどうか？ enum Either<A, B> { case left(A) case right(B) } ↓ Bool, Three Either<Bool, Either<Bool, Either<Bool, Either<Bool, Either<Bool, なら（2 + 3）パターン Three>.left(true) Three>.left(false) Three>.right(.one) Three>.right(.two) Three>.right(.three) 18

enum はどうか？ enum Either<A, B> { case left(A) case right(B) } ↓ Bool, Void なら（2 + 1）パターン Either<Bool, Void>.left(true) Either<Bool, Void>.left(false) Either<Bool, Void>.right(Void()) 19

enum はどうか？ enum Either<A, B> { case left(A) case right(B) } ↓ Never なら？ Either<Bool, Never>.left(true) Either<Bool, Never>.left(false) Either<Bool, Never>.right(???) // Either コードとしては有効ではない（説明のため） を使うと、⽚⽅の case は無になる 20

まとめると Either<Bool, Either<Bool, Either<Bool, Either<Bool, Bool> Three> Void> Never> = = = = 4 5 3 2 = = = = 2 2 2 2 + + + + 2 3 1 0 の値は「A の値の数 + B の値の数」 これが enum が 「sum types」と呼ばれる所以である Either は論理学の観点から解釈することもできる ⼆つの型の「または」を取る意味をカプセル化している Either<A, B> 21

気をつけるべきこと などの⾔語では Void の扱いが異なる Void で無⼈型（ uninhabited type ）を表現している Swift では Never に当たる 他の⾔語と混同しないように注意しましょう Haskell, PureScript 22

⼀意な値を持つ型の名前として Unit を定義 struct Unit {} // Void let unit = Unit() Unit の代わりとなるものを定義 を定義したことによる利点は ↓ のように拡張できること extension Unit: Equatable { static func == (lhs: Unit, rhs: Unit) -> Bool { return true } } これで等価な値だけを求める関数に値を渡すことができる 23

Void Void は拡張できない で extension しようとすると ↓ のようなエラーが起きる Non-nominal type 'Void' cannot be extended なぜなら Void は空のタプルとして定義されている typealias Void = () タプル は Swift において nominal types ではなく、 structural types であるため、 extension できない 24

Unit と Never の定義を並べてみる struct Unit {} enum Never {} 「フィールドを持たない struct」と「case を持たない enum」 という対称性が明らかにある しかし、struct には値が⼀つあって、enum には値がないのは なぜなのか？ Swift の型と代数の対応関係を持って、この謎を解くための 質問をすることができる 25

空の struct と enum にはどんな値がある？ 例えば let xs = [1, 2, 3] のような整数の配列があったとして、 ↓ のような関数を定義するにはどうすれば良いか？ func sum(_ xs: [Int]) -> Int { fatalError() } func product(_ xs: [Int]) -> Int { fatalError() } sum(xs) product(xs) 26

例えばこのように実装できる func sum(_ xs: [Int]) -> Int { var result: Int // result for x in xs { result += x } return result } が定義されていないのでコンパイルはできない func product(_ xs: [Int]) -> Int { var result: Int // for x in xs { result *= x } return result } こちらも同じ。しかし、result には何を⼊れるべきなのか？ 27

result には何を⼊れるべき？ この質問に答えるためには、和と積が満たすべき性質を理解する 必要がある （もちろんこの問題は簡単であるため、理解せずとも解くことが 可能ではある） そのためには、配列の連結について sum と product が どのように振る舞うかを考えれば良い 28

sum と product にはどう振る舞って欲しい？ 普通の⾃然数の場合 sum([1, 2]) + sum([3]) == sum([1, 2, 3]) product([1, 2]) * product([3]) == product([1, 2, 3]) もし空の配列を考えたら ↓ のようになるはず sum([1, 2]) + sum([]) == sum([1, 2]) product([1, 2]) * product([]) == product([1, 2]) 29

代数学を使って先ほどの問題が解ける さっきの例 sum([1, 2]) + sum([]) == sum([1, 2]) product([1, 2]) * product([]) == product([1, 2]) このことから ↓ は強制される 空の和型（enum）には値がない 空の積型（struct）には値が⼀つしかない sum([]) == 0 // product([]) == 1 // 代数学を使って（簡単に？）解くことができた 30

答えがわかったので関数に適⽤してみる func sum(_ xs: [Int]) -> Int { var result: Int = 0 // for x in xs { result += x } return result } 空の和型なので 0 を初期値とする func product(_ xs: [Int]) -> Int { var result: Int = 1 // for x in xs { result *= x } return result } 空の積型なので 1 を初期値とする 31

徐々にレベルの⾼い構⽂についても考えていく の型と代数の対応関係を理解するための概念が構築できた より⾼いレベルでもその直感を活かすことができるかを⾒ていく その前に、もう少し簡単なところからはじめていく Swift 32

Void Void について⾒てみる は 1 に対応し、代数の世界では 1 を掛けても何も起きない // Void = 1 // A * Void = A = Void * A 型の世界で考えると？ struct のフィールドで Void を使⽤しても基本的には 型を変更せずに済むということ 33

Never についても⾒てみる は 0 に対応し、代数の世界では 0 を掛けると 0 になる 型の世界では ↓ のようになる Never // Never = 0 // A * Never = Never = Never * A つまり、型の世界において struct のフィールドに Never を⼊れる と、その構造体⾃体が Never 型になってしまうという結果になる これは構造体を完全に消滅させることを意味する 34

和の場合はこのようになる の場合 0 を追加する、つまり値を変更せずに残すという結果になる Never // A + Never = A = Never + A 1 を追加するということは、Void を追加するという意味になる // 1 + A = Void + A 35

1 + A = Void + A この式は Either を使えば ↓ のように表すことができる // Either<Void, A> { // case left(()) // case right(A) //} つまり、これは右辺に A の値が全て存在して、そこに⼀つの特殊な 値である left(Void()) が隣接している型であると捉えられる 36

Swift にはこのような型が存在している // Either<Void, A> { // case left(()) // case right(A) //} これと似ている Swift の型 -> Optional enum Optional<A> { case none case some(A) } 37

この考えを使えば？ 先ほど⾒た ↓ の式は // 1 + A = Void + A このように表すことができる // Void + A = A? 38

代数を⽤いることで型が簡潔になる例 // Either<Pair<A, B>, Pair<A, C>> ↓ // A * B + A * C これは因数分解すると A(B + C ) と表すことができる。つまり Swift では ↓ のように直せる // Pair<A, Either<B, C>> 39

他にも⾒てみる // Pair<Either<A, B>, Either<A, C>> 数学の世界では (A + B)(A + C ) これ以上因数分解はできないため、Swift でさらに簡潔に表すことは できない。もちろん展開して考えることはできる このように代数学はデータ構造を考えるための⼀つの⼿段となる 40

今⽇やったことは結局何の役に⽴つのか？ 今⽇は有効な Swift でさえない疑似コードの束を並べていただけ 直感のためには役⽴つことがわかったが、エンジニアにとって メリットはあるのか？ 41

URLSession は Swift を活かしきれていない URLSession.shared .dataTask(with: url, completionHandler: (data: Data?, response: URLResponse?, error: Error?) -> Void) は全て Optional の値を返す また、Swift のタプルは単なる積であるため、以下のように考える completionHandler // (Data + 1) * (URLResponse + 1) * (Error + 1) 42

これを展開してみる // (Data + 1) * (URLResponse + 1) * (Error + 1) // 2 * 2 * 2 = 8 // = Data * URLResponse * Error // // + Data * URLResponse // + URLResponse * Error // // + Data * Error // // + Data // + URLResponse // + Error // + 1 // Void nil の状態がある これは絶対起きてはいけない これも同時に存在してはいけない（議論あり） これも同時に存在してはいけない これはただの であり、この場合は全て である これを考慮するとすれば、予想されるケースを越える場合、必然的に fatalError が必要となってしまう。開発者は、 data ・ response ・ error を扱えば良いだけではあるが、API 内部では無駄が多い 43

代数学の直感を使い、適切な型を探る 直感を使って本当に欲しいものを表現してみると ↓ のようになる // Data * URLResponse + Error さっきまで使っていた型を利⽤すれば ↓ のような感じ // Either<Pair<Data, URLResponse>, Error> 44

Swift Swift の Result では、先ほどのような状態を扱えるものがある // Result<(Data, Response), Error> このように callback で適切な型を使⽤すれば、コンパイル時に 許可される無効な状態の数を⼤幅に減らすことができる callback で必要とされるロジックを単純化することができる 45

Result 型についてさらに考えてみる 失敗することのない特定の操作を⾏う場合は？ // Result<A, Never> でエラーケースは存在しないことが証明できた キャンセルをサポートする⾮同期 API を使っている場合は？ ↑ // Result<A, Error>? Optional にするだけ 46

URLSession に対する議論について補⾜ // (Data + 1) * (URLResponse + 1) * (Error + 1) // 2 * 2 * 2 = 8 // = Data * URLResponse * Error // // + Data * URLResponse + URLResponse * Error // // + Data * Error // // + Data // + URLResponse // + Error // + 1 // Void nil の状態がある これは絶対起きてはいけない これは存在してはいけないと述べられていた これも同時に存在してはいけない これはただの であり、この場合は全て である の読者である Ole Begemann によって、存在する可能性が あることが指摘されていた Point-Free 47

URLResponse * Error がなぜ存在するか はサーバの HTTP レスポンスヘッダをカプセル化 している URLSession API は有効なレスポンスヘッダを受信すると、 後の段階（キャンセルやタイムアウトなど）でリクエストが エラーになっても、常に URLResponse を提供する つまり、URLResponse と Error は共存しうる didReceiveResponse と didReceiveData のための別のデリゲート メソッドがあるため、これが⾃然だと思う⼈もいるかもしれない URLReponse 48

のドキュメントでも⾔及がある “ If a response from the server is received, regardless of whether the request completes successfully or fails, the response parameter contains that information. “ URLSession サーバからの応答を受信した場合、リクエストが正常に完了したか失 敗したかに関わらず、応答パラメータにはその情報が含まれます。 この議論についてのそれぞれの⾒解があるので⾒てみると⾯⽩い Point-Free: #9 Algebraic Data Types: Exponents Ole Begemann: Making illegal states unrepresentable 49

今⽇のまとめ 代数学を使えば、複雑さをどうにかして処理し、⾃分のニーズに 合った型に⾃然に誘導できることがわかった 代数学的な直感が⽇常のコードを改善できる可能性が⾒えた 代数はまだまだ Swift に応⽤して考えることができる TCA の後々の章では指数・再帰などについても⾒ていくらしい 代数学と Swift の関係性が⾒えた気分になって、Swiftの⾒⽅が 広がった気がします 50