圏論とSwiftへの応用 / iOSDC Japan 2018

iOSDC Japan 2018 (Sep 2, 2018)

https://iosdc.jp/2018/
https://fortee.jp/iosdc-japan-2018/proposal/45b858e0-753c-4387-9210-5837cff6da7a

iOSDC Japan 2018 「圏論とSwiftへの応用」発表スライドメモ - Qiita
https://qiita.com/inamiy/items/3e0c10d5eaf234b41c3d

iOSDC Japan 2018 で発表した「圏論とSwiftへの応用」の補足 - Qiita
https://qiita.com/inamiy/items/c4e85f22273e98b8db26

エラッタ：
p60. https://twitter.com/inamiy/status/1413894710372888577

Transcript

1. ݍ࿦ͱɹɹɹ Swift΁ͷԠ༻ 2018/09/02 iOSDC 2018 Yasuhiro Inami / @inamiy
4. ݍ࿦ Category Theory
6. ݍ࿦ͱ͸ʁ • ʮ఺ʯͱʮ໼ҹʯΛ࢖ͬͨ਺ֶͷ Foundation.framework • ఺ΑΓ΋໼ҹͷํ͕ॏཁʢू߹࿦ͷߟ͑ํͱ͸ٯʣ • Ԡ༻ൣғ͕޿͍ɿ ਺ֶɺ࿦ཧֶɺܭࢉػՊֶɺཧ࿦෺ཧֶɺ ೝ஌Պֶɺ఩ֶɺੜ෺ֶɺetc • ਺ֶͷ஌͕ࣝθϩͰ΋ֶ΂Δʢඍੵɺઢܗ୅਺΋͍Βͳ͍ʣ • ؔ਺ܕϓϩάϥϛϯάͰେ׆༂
7. ݍ࿦ΛֶͿ → ܕγεςϜ νϣοτσΩϧ • ࠶ؼܕʢෆಈ఺ɺfixɺreduce (fold) / sequence (unfold)ʣ • શশྔԽ ʢύϥϝʔλଟ૬ɺδΣωϦΫεʣ • ଘࡏྔԽ ʢϓϩτίϧ (existential container)ʣ • ߴϥϯΫଟ૬ʢଟ૬ؔ਺ΛҾ਺ͱͯ͠࢖͑Δʣ • ߴΧΠϯυଟ૬ʢܕίϯετϥΫλΛܕҾ਺ͱͯ͠࢖͑Δʣ • ґଘܕʢ஋ʹґଘ͢Δܕ͕࡞ΕΔʣ
8. ݍ࿦ΛֶͿ ↓ ʮܕʯΛ ΑΓਂ͘ཧղͰ͖Δ ↓ Swiftͷݱঢ়ͱ ະདྷ͕ݟ͑ͯ͘Δ
9. ※ ͓அΓ ͜ͷεϥΠυͰ͸ɺ ʮٙࣅSwiftʯΛ࢖ͬͯղઆ͍ͯ͠·͢ɻ ( Swift 4.2ݱࡏɺݴޠػೳ͕଍Γͳ͍ͨΊ)
10. ݍͷఆٛ Definition
21. ݍͷఆٛ • ର৅ (object)ɿ • ࣹ (morphism)ɿ • ߃౳ࣹ (identity)ɿ • ߹੒ (composition)ɿ • ݁߹཯ (associativity)ɿ • ࢝Ҭ (domain) / ऴҬ (codomain):
22. Swift ͷྫ // ߃౳ࣹʢྫɿ `f ⚬ id == f`ɺ `id ⚬ f == f`ʣ func id<A>(_ a: A) -> A { return a } // ؔ਺ͷ߹੒ʢྫɿ `(g ⚬ f)(x) == g(f(x))`ʣ func ⚬ <A, B, C>(_ g: B -> C, _ f: A -> B) -> A -> C { return { g(f($0)) } }
23. ؔख Functor
31. ؔख (Functor) • ݍΛʮର৅ʯʹɺ ͋Δݍ͔Β͋Δݍ ΁ͷߏ଄ʢ໼ҹશମͷܗʣΛอͭ ʮࣹʯʢϚοϐϯάʣ • ֤ର৅ ʹ͍ͭͯ ʹରԠ • ֤ࣹ ʹ͍ͭͯ ʹରԠ • ߏ଄ʢ߹੒ͱ߃౳ࣹʣΛอଘ͢Δ • •
32. // ٙࣅSwift protocol Functor[F] { // Note: `self.map { ... }` ʢΠϯελϯεϝιουʣ // ͱͯ͠΋࢖͑Δͱ͢Δ static func map<A, B>(_ self: F<A>, _ f: A -> B) -> F<B> } extension Functor[Array] { ... } // ࢖༻ྫɿ Array<Int> ==> Array<String> [1, 2, 3].map(String.init) == ["1", "2", "3"]
33. ؔखͱ͸ʮmap ͕Ͱ͖Δʯ͜ͱ map = ίϯςφΛม͑ͣʹ த਎Λม͑Δʁ ʢର৅͕த৺ (pointwise) ͷߟ͑ํʣ
34. // લܝ protocol Functor[F] { static func map<A, B>(_ self: F<A>, _ f: A -> B) -> F<B> } // Ҿ਺ॱংΛೖΕସ͑ͯɺΧϦʔԽ͢Δͱɾɾɾ protocol Functor[F] { // ؔ਺্࣋ͪ͛ (lifting) static func map<B>(_ f: A -> B) -> F<A> -> F<B> } map ͕ f: A -> B ͔Β F(f): F<A> -> F<B> ΁ͷม׵ʹͳΔ
36. map ʢؔखʣ͸ɾɾɾ ݍͷؔ਺ f Λɺผͷݍͷؔ਺ F(f) = map(f) ʹࣸ͢ ʢࣹ͕த৺ (pointfree) ͷߟ͑ํʣ
37. ͷҙຯ 2ͭͷࣹ ʹ͍ͭͯɺઌʹ߹੒͔ͯ͠Β Λద༻ͯ͠΋ɺ ΛͦΕͧΕʹద༻͔ͯ͠Β߹੒ͯ͠΋ಉ͡
38. ͷྫ let count: String -> Int = { $0.count } let isEven: Int -> Bool = { $0 % 2 == 0 } ["Hello"].map(isEven ⚬ count) // ؔ਺߹੒ ʴ 1ճ `map` == ["Hello"].map(count).map(isEven) // 2ճ `map` // ==> F.map(isEven ⚬ count) == F.map(isEven) ⚬ F.map(count) ! 2ճ map͸ɺʮؔ਺߹੒ʴ1ճ mapʯͱಉ͡ʢܭࢉྔ࡟ݮʣ
39. ༨ஊɿࣗݾؔख (Endofunctor) ͜͜·Ͱɺ Array<Int> ΍ Array<String> Λɺ Int ΍ String ͱ͸ ผͷݍʢArray ͷݍʣ ͷର৅ͱͯ͠ߟ͖͑ͯͨ ɹɹɹɹɹɹɹɹɹɹɹɹɹˣ ࣮ࡍ͸ɺ͢΂ͯಉ͡SwiftͷܕͳͷͰɺ1ͭͷʮSwiftݍ ʯͷର৅ ͱͯ͠ѻͬͯྑ͍ ɹɹɹɹɹɹɹɹɹɹɹɹɹˣ ϓϩάϥϛϯάͷੈքͷ ؔख (Functor) ͱ͸ɺ࣮͸ ࣗݾؔख ʢݍ͔Βಉ͡ݍ΁ͷؔख ʹ ଟ૬ؔ਺ mapʣ ͷ͜ͱ
41. ࣗવม׵ Natural Transformation
45. ࣗવม׵ • 2ͭͷݍͷؒͷ"ࣹ"Ͱ͋ΔؔखΛʮର ৅ʯͱͯ͠ѻͬͨͱ͖ͷɺؔख͔Β ؔख΁ͷʮࣹʯ • ݍ ͱؔख ͕༩͑ ΒΕͨͱ͖ɺࣗવม׵ ͸ ͷࣹ ͷू߹ Ͱɺ೚ҙͷ ʹରͯ͠ɺҎ Լͷ౳ࣜʢՄ׵ਤࣜʣ Λຬͨ͢ɿ
46. ͷҙຯ // ࣗવม׵ʢத਎Λม͑ͣʹίϯςφΛม͑Δʮଟ૬ؔ਺ʯʣ func alpha<A>(_ fa: F<A>) -> G<A> { ... } // Մ׵ࣜ alpha(fa.map(f)) == alpha(fa).map(f) // ==> alpha ⚬ F.map(f) == G.map(f) ⚬ alpha ! F.map(f) Λઌʹܭࢉ͔ͯ͠Β alpha Λܭࢉͯ͠΋ɺalpha Λઌʹܭࢉ͔ͯ͠Β G.map(f) Ͱ΋ɺͲͪΒͰ΋੒Γཱͭ
47. ͷྫ /// Array -> Optional ΁ͷࣗવม׵ func arrFirst<A>(_ arr: Array<A>) -> Optional<A> { return arr.first } arrFirst( [1, 2, 3].map(String.init) ) // `map` ͔ͯ͠Β `first` == arrFirst([1, 2, 3]).map(String.init) // `first` ͔ͯ͠Β `map` ! ӈลͷํ͕ܭࢉྔ͕গͳ͍ → ίϯύΠϥ͕࠷దԽͰ͖Δ
48. ถాͷิ୊ Yoneda Lemma
55. ถాͷิ୊
56. ถాͷิ୊ ʹʮࣗવม׵ʯͱʮ஋ʯͷ1:1ରԠ let fa: F<A> = ... // ஋ func closure<B>(_ f: A -> B) -> F<B> { // ࣗવม׵ return fa.map(f) // `fa` Λ಺෦Ͱ࣋ͭ } faʢ஋ʣͱ closureʢ஋Λดแͨ͠ଟ૬ؔ਺ʣ͸"ಉ͡΋ͷ"ɺ ͦΕΒͷܕ͸ ಉܕʢ૬ޓʹม׵Մೳʣ ͱΈͳͤΔ
57. // F(A) ͔Β ∀B. (A -> B) -> F(B) ΁ͷม׵ func faToClosure<A, B>(_ fa: F<A>) -> (A -> B) -> F<B> { return { f in return fa.map(f) } } // ∀B. (A -> B) -> F(B) ͔Β F(A) ΁ͷม׵ func closureToFa<A>( _ closure: /* ϥϯΫ2ଟ૬ */ <B> (A -> B) -> F<B> ) -> F<A> { return closure(id) }
58. ࢀߟεϥΠυ2ɿ ಉܕͷ࿩ 2 https://speakerdeck.com/inamiy/algebraic-data-type-in-swift ༨ஊɿถాͷิ୊Λ࢖͏ͱ ͷࢦ਺๏ଇ΍ɺ෼഑๏ଇͳͲ͕؆୯ʹূ໌Ͱ͖·͢
59. ถాͷิ୊͔Βɺܧଓ (CPS) ͱCPSม׵ • ʢ߃౳ؔखʣͱ͓͘ͱɺCPSʢܧଓʣ • ͱ͓͘ͱɺCPSม׵ʢʹ ถాຒΊࠐΈ ʣ func cpsTransform<A, B, X>(_ f: X -> A) -> (A -> B) -> (X -> B) { return { aToB in return { x in aToB(f(x)) } } }
60. func fac(_ n: Int) -> Int { // ⚠ ຤ඌ࠶ؼͷܗͰ͸ͳ͍ʢ͕ɺཪͰίϯύΠϥ͕࠷దԽͯ͘͠ΕΔʣ return n == 0 ? 1 : n * fac (n - 1) } // `cpsTransform` Λ࢖Θͣɺखॻ͖ͰܧଓʹΑΔ຤ඌ࠶ؼ func facCPS<R>(_ n: Int, _ next: Int -> R) -> R { return n == 0 ? next(1) : facCPS(n - 1, { next(n * $0) }) } // `cpsTransform` Λ࢖ͬͨ৔߹ʢ຤ඌ࠶ؼ࠷దԽʣ let facCPSAuto: (Int -> Int) -> Int -> Int = cpsTransform(fac) facCPS(4, id) // 24 ʢखಈͰ຤ඌ࠷దʣ facCPSAuto(id)(4) // 24 ʢࣗಈͰ຤ඌ࠷దʣ
61. ਵ൐ Adjunction
65. ਵ൐
66. ࣗ༝ؔख ๨٫ؔख
67. // ٙࣅSwift protocol Adjunction[F, U] where Functor[F], Functor[U] { /// (F(C) -> D) -> (C -> U(D)) static func leftAdjunct<C, D>(_ f: F<C> -> D) -> C -> U<D> /// (C -> U(D)) -> (F(C) -> D) static func rightAdjunct<C, D>(_ f: C -> U<D>) -> F<C> -> D }
68. ਵ൐ͷྫ /// ੵͷܕʢλϓϧʣ typealias Tuple<A, B> = (B, A) // ஫ҙɿ޲͖͕ٯ /// ؔ਺ͷܕʢReaderͱ΋ݺ͹ΕΔʣ typealias Func<A, B> = A -> B
69. extension Functor[Tuple<A>] { // `Tuple<A>` ͸ `A` ͷΈͷ෦෼ద༻ static func map(_ f: C -> D) -> Tuple<A, C> -> Tuple<A, D> { return { t in return (f(t.0), t.1) } } } extension Functor[Func<A>] { static func map(_ f: C -> D) -> Func<A, C> -> Func<A, D> { return { fun in return f ⚬ fun } } }
70. // Tuple<A> ⊣ Func<A> extension Adjunction[Tuple<A>, Func<A>] { static func leftAdjunct<C, D>(_ f: Tuple<A, C> -> D) -> C -> Func<A, D> { return { c in { a in f((c, a)) } } } static func rightAdjunct<C, D>(_ f: C -> Func<A, D>) -> Tuple<A, C> -> D { return { t in f(t.0)(t.1) } } }
71. func curry<A, B, C>(_ f: (A, B) -> C) -> A -> B -> C { return { a in return { b in return f(a, b) } } } func uncurry<A, B, C>(_ f: A -> B -> C) -> (A, B) -> C { return { a, b in return f(a)(b) } }
72. leftAdjunct == curry rightAdjunct == uncurry (Tuple<A> ⊣ Func<A> ͷͱ͖)
73. ਵ൐ͷผͷఆٛ
80. extension Adjunction { static func unit<C>(_ c: C) -> U<F<C>> { // `leftAdjunct` ͷୈ1Ҿ਺͸ `F<C> -> D` ͳͷͰɺ // `id` Λద༻͢Δͱɺܕͱͯ͠ `D = F<C>` ͕֬ఆ͢Δ return leftAdjunct(id)(c) } static func counit<D>(_ fud: F<U<D>>) -> D { return rightAdjunct(id)(fud) } }
81. counit: F<U<D>> -> D ʹɺ D = F<C> Λ୅ೖͯ͠ΈΔͱ counit: F<U<F<C>>> -> F<C> ͜ΕΛ͞Βʹ ؔख U ͰϦϑτ͢Δͱ U.map(counit): U<F<U<F<C>>>> -> U<F<C>> extension Adjunction { static func join<C>(_ x: U<F<U<F<C>>>>) -> U<F<C>> { return map(counit) } }
82. ੔ཧͯ͠ΈΔɿ extension Adjunction { static func unit<C>(_ c: C) -> U<F<C>> { return leftAdjunct(id)(c) } static func join<C>(_ x: U<F<U<F<C>>>>) -> U<F<C>> { return map(counit) } } ͜͜Ͱɺ U<F<C>> = M<C> ͱஔ͍ͯΈΔͱɾɾɾ
83. protocol Monad[M] where Functor[M] { static func unit<C>(_ c: C) -> M<C> static func join<C>(_ mmc: M<M<C>>) -> M<C> } extension Monad { static func flatMap<C, C2>(_ f: C -> M<C2>) -> M<C> -> M<C2> { return { (join ⚬ map(f))($0) } } }
84. Ϟφυ Monad
85. ਵ൐ ↓ Ϟφυ
86. ྫɿ Tuple<S> ⊣ Func<S> ΑΓɺ Func<S, Tuple<S, A>> ʹʮؔ਺ͷதʹλϓϧΛೖΕΔʯʹ ঢ়ଶϞφυ struct State<S, A> { let runState: S -> (A, S) init(_ fun: Func<S, Tuple<S, A>>) { // `Func<S, Tuple<S, A>>` ͱ // `S -> (A, S)` ͸࣮͸ಉ͡ʂ self.runState = fun } }
87. ͸Ϟφυ Ͱ͸ɺٯͷ ͸lĤĤĤ
88. // W ͸ Ϟφυ M ͷٯ protocol Comonad[W] where Functor[W] { // Ϟφυͷ `unit: C -> M<C>` ͷٯ static func counit<D>(_ wc: W<D>) -> D // Ϟφυͷ `join: M<M<C>> -> M<C>` ͷٯ static func duplicate<D>(_ wc: W<D>) -> W<W<D>> }
90. ༨Ϟφυ Comonad
91. ਵ൐ ↓ ༨Ϟφυ
92. ྫɿ Tuple<A> ⊣ Func<A> ΑΓɺ Tuple<A, Func<A, S>> ʹʮλϓϧͷதʹؔ਺ΛೖΕΔʯʹ ༨ঢ়ଶ༨Ϟφυ struct Store<A, S> { // CoState ͱ΋ݴΘΕΔ let setter: A -> S let getter: A init(_ t: Tuple<A, Func<A, S>>) { self.setter = t.0 self.getter = t.1 } }
93. ͦͯ͠ɺ S -> Store<A, S> ʢ༨୅਺ɺCoalgebraʣΛߟ͑Δ struct Lens<A, S> { let setter: S -> A -> S let getter: S -> A init(_ f: S -> Store<A, S>) { self.setter = { s in f(s).setter } self.getter = { s in f(s).getter } } }
94. Ϩϯζ͸ ༨ঢ়ଶ༨Ϟφυͷ ༨୅਺ Lenses are Costate Comonad Coalgebras
95. ·ͱΊ • ݍɺ߹੒ɺ߃౳ࣹ • ؔख (Functor) → ݍͷࣹΛɺผͷݍʹࣸ͢ (map) • ࣗવม׵ (Natural Transformation) → Մ׵ਤࣜɺଟ૬ؔ਺ • ถాͷิ୊ (Yoneda Lemma) → ܧଓ (CPS) ͳͲ • ਵ൐ (Adjunction) → ΧϦʔԽɺϞφυɺ༨Ϟφυ • Ϟφυ / ༨Ϟφυ ((Co-)Monad) → ঢ়ଶϞφυɺϨϯζ
96. ͞ΒʹֶͿͨΊʹ • ۃݶ (Limit) l ੵɺΠίϥΠβɺҾ͖໭͠ɺetc • Τϯυ / ༨Τϯυ (End / Coend) • ୅਺ / ༨୅਺ (Algebra / Coalgebra) • ࣗ༝ؔखɾࣗ༝Ϟφυ (Free Functor, Free Monad) • Χϯ֦ு (Kan Extension) • ϞϊΠυݍɾ๛য়ݍ (Monoidal / Enriched Category)
97. ࢀߟจݙʢॳֶऀ޲͚ʣ • Bartosz Milewski's Programming Cafe | Category Theory, Haskell, Concurrency, C++ • ! Bartosz Milewski - YouTube • ! TheCatsters - YouTube • Category theory for beginners • ݍ࿦ษڧձ @ ϫʔΫεΞϓϦέʔγϣϯζ
98. ࢀߟจݙʢதʙ্ڃऀ޲͚ʣ • ! ݍ࿦ ݪஶୈ2൛ | Steve Awodey • ! ϕʔγοΫݍ࿦ ීวੑ͔Βͷ଎शίʔε | Tom Leinster • ! ݍ࿦ͷجૅ | Saunders MacLane • ݍ࿦ | ұେ੔Ҭ • ᐻࢁਖ਼޾ͷΩϚΠϥࣂҭه • nLab
99. Thanks! Yasuhiro Inami @inamiy