計算で解くには、現在の最高性能のスーパーコンピューターでも少なくとも10の50乗年かかる。量子コンピューターに対しても十分な安全性を確保できる見込みだ。既存の様々な通信システムのソフトウエアを変えるだけで、そのまま使える。 米国立標準技術研究所(NIST)は量子コンピューターでも解読できない次世代暗号技術の標準化を進めており、情通機構の新技術は候補に選ばれた。今後3年以上かけて標準が決まる見通し。採用されれば国際的に普及する可能性が高い。
コンピュータ上でのテキストとして表記する場合、フォントによっては↑のような記号が無い場合もあるため、a^^bのようにサーカムフレックスを並べる表記を行う場合がある。クヌース自身も、これを代替的あるいは簡便な記法として認めている。
https://ja.wikipedia.org/wiki/%E3%82%AF%E3%83%8C%E3%83%BC%E3%82%B9%E3%81%AE%E7%9F%A2%E5%8D%B0%E8%A1%A8%E8%A8%98 Swift で作ってみた。 ^
は別の演算子なので Python 等に倣って **
で代用。 precedencegroup UpArrowPrecedence { higherThan: MultiplicationPrecedence associativity: right } infix operator ** infix operator ^^ infix operator ^^^ func **(lhs: Int, rhs: Int) -> Int { return uparrow(lhs, rhs, *) } func ^^(lhs: Int, rhs: Int) -> Int { return uparrow(lhs, rhs, **) } func ^^^(lhs: Int, rhs: Int) -> Int { return uparrow(lhs, rhs, ^^) } private func uparrow(_ lhs: Int, _ rhs: Int, _ operation: (Int, Int) -> Int) -> Int { precondition(rhs >= 0) var result = 1 for _ in 0..<rhs { result = operation(lhs, result) } return result } print(2 ** 3) // 8 print(2 ^^ 3) // 16 print(2 ^^^ 3) // 65536
reduce
で書きたかったんだけど(それなら initialValue
を明示的に指定することになる)、同じ値を繰り返す Sequence
を簡単に作る方法が思いつかなかった( Array.init(repeating:count:)
みたいに実体を作る方法ではなく)。何かあったっけ?さて、 Either<T, U> の値域は、 任意の t∈T, u∈U に対して、 a == t || b == u を満たすパターンの集合だと言える。
ここの ||
が XOR になりませんか? a is T && b is U
のときの値を表せないように思います。 (edited)a is T || b is U
かなと思うんですよ。 a is T
が成り立ったたら、 ||
の後ろは判定できませんよね。||
や &&
を短絡評価の意味合いで使ってるんですね。a == t || b == u
を満たす (a,b) の集合ではなくて、 a == t || b == u
を満たすパターンの集合ですよ。パターンの集合って言葉がおかしいけど。Either<A, A>
を考えればそんな気もしてきました。Pair<T, U>
→ Tの値を持っている && Uの値を持っている Either<T, U>
→ Tの値を持っている Uの値を持っている と言えばよかったのかも。無理に && と を使って説明するには。||
じゃなくて XOR になってしまって ||
に対応するのは These<T, U>
になってしまうから「値的に」ではなく「型的に」ということなんじゃないでしょうか? (edited)(T?, U?) | | T | N | |:-:|:-:|:-:| | U | o | o | | N | o | o | Either<T, U> | | T | N | |:-:|:-:|:-:| | U | | o | | N | o | | These<T, U> | | T | N | |:-:|:-:|:-:| | U | o | o | | N | o | |
#swift @koher より引用 (edited)(T, U)
| | T | N | |:-:|:-:|:-:| | U | o | | | N | | |
(T, U)
は論理積に対応するけど Either<T, U>
より These<T, U>
が論理和に対応するように見えるという話でした。Either<T, U>
において「値TとUが別々の場所に格納される」わけではないですし。T
| | T | N | |:-:|:-:|:-:| | U | | | | N | o | |
Either<A, B>
のようなのが sum type なのに、↑の表を見てると論理和の表と対応しないぞ?論理和と sum type の関係は?って考えてた与太話ですEither
は標準ライブラリにないですが作ればできます。T
| | T | N | |:-:|:-:|:-:| | U | o | | | N | o | |
T|U
の話がまさに値と型を混同していて、 T|U
は T
と U
の値を同時に保持できないけど、 T&U
の値は保持できる。T
だけを考えるということが意味をなさないところが、型と値の混同具合を表してますかね。集合論において、集合の族の直和 (英: direct sum) は、以下の緊密に関連した二種類の概念を指して用いられる。 - 識別された和 (discriminated union): 通常の合併の操作を少し改変して、合併に属する元がもともとどの集合に入っていたか識別することができるようにしたもの。 - 交わりを持たない和 (disjoint union): その族に属する部分集合のどの二つも互いに素 (pairwise disjoint) であるときの、通常の合併。 … 本項においては主に前者について扱い、それを非交和と呼称する。
https://ja.wikipedia.org/wiki/%E9%9D%9E%E4%BA%A4%E5%92%8C (edited)圏 C の二つの対象 X1, X2 に対し、それら二つの対象の余積 X1 ∐ X2(または X1 ⊕ X2 あるいは単に X1 + X2 と書くこともある)とは
記号ばらつきすぎwEquatable
であることが仮定されているのかな?当然っちゃ当然だけど、そういう定義って見たことがない気が。自明だから?プログラミング的に考えたら、 Set<T>
に求められる操作を考える過程で T : Equatable
と Set<T> : Equatable
が導かれる気がする。 (edited)例えば,群には部分群・正規部分群・ 商群,環には部分環・イデアル・商環,ベクトル空間には部分空間・商空間といった,よく 似た構造があり,群論・環論・線形代数のどの理論でも準同型定理と呼ばれるそっくりの定 理が成り立ちます.準同型定理はどの理論でもほぼ同様のルーチンワークで証明できます. また,いま挙げたどの理論にも直積と呼ばれる構造があって,直積の一意性は同様のルーチ ンワークで証明できます.圏論は,こういったさまざまな理論に見られる相似構造を抽出し て,まとめて面倒を見ることができます.
もちろんこの講演ノートだけでは,圏論の解説としては まったく不十分ですが,圏論の本を恐れずに読めるくらいの準備は提供できたのでないかと 私は期待します.
とのことですが、これまで圏や射の定義すらよくわからなかったので、そこが定義と例でわかりやすく説明されていたのがよかったです。圏論の歩き方委員会(編著),『圏論の歩き方』,日本評論社 (2015). 数学セミナーに連 載された記事を単行本化したものです.(たぶん)12 人の参加者による,リレー形式, ときには対談形式で,多様な視点から圏論へのアプローチを紹介するガイドブックの ような書物です.こういう本を形にすること自体,非常に面白い試みだと思うのです が,圏論の教科書として通読するのには向いていないかもしれません.
とありますが、僕もこれが妥当な評価だと思います。 (edited)学部の量子力学の演習中に「(講義担当の)先生の量子力学の教え方は古い」と私が友人にささやいたのを先生に聞き取られ(私の声が大きすぎた),だったら君が講義してみろと先生に言われ(「君が一番わかりやすいと思うやり方で君が講義してもいいよ」という優しい言い方だったと思います),その場で(応用物理学科の教室で)量子力学の講義をしたことがありました。いま思い返しても自分は生意気な学生だったと思います。
http://www.phys.cs.is.nagoya-u.ac.jp/~tanimura/// proof4 : succ(succ(zero)) = succ(zero) + succ(zero) let proof4 : Eq<Succ<Succ<Zero>>,Add<Succ<Zero>, Succ<Zero>>> = transitive(s:Add<Succ<Zero>,Succ<Zero>>.self,t: Succ<Add<Succ<Zero>, Zero>>.self,r: Succ<Succ<Zero>>.self)(proof1)(proof3)
(edited)// proof4 : succ(succ(zero)) = succ(zero) + succ(zero) let proof4 : Eq<Succ<Succ<Zero>>,Add<Succ<Zero>, Succ<Zero>>> = transitive(proof1)(proof3)
func transitive<S,T,R>(s:S.Type = S.self, t:T.Type = T.self ,r:R.Type = R.self) -> (Eq<S,T>) -> (Eq<T,R>) -> Eq<R,S>
// proof1 : succ(zero) + succ(zero) = succ(zero + succ(zero)) // use axiom3 let proof1 : Eq<Add<Succ<Zero>,Succ<Zero>>, Succ<Add<Succ<Zero>,Zero>>> = axiom3() // proof2 : succ(zero) + zero = succ(zero) let proof2 : Eq<Add<Succ<Zero>, Zero>, Succ<Zero>> = axiom2() // proof3 : succ( succ(zero) + zero ) = succ(succ(zero)) let proof3 : Eq<Succ<Add<Succ<Zero>, Zero>>,Succ<Succ<Zero>>> = axiom1()(proof2) // proof4 : succ(succ(zero)) = succ(zero) + succ(zero) let proof4 : Eq<Succ<Succ<Zero>>,Add<Succ<Zero>, Succ<Zero>>> = transitive()(proof1)(proof3) // proof5 : succ(zero) + succ(zero) = succ(succ(zero)) let proof5 : Eq<Add<Succ<Zero>, Succ<Zero>>,Succ<Succ<Zero>>> = symmetric()(proof4)
結合律: f: a → b, g: b → c, h: c → d ならば h ∘ (g ∘ f) = (h ∘ g) ∘ f が成り立つ。 単位律: 各対象 x ∈ ob(C) に対して x の恒等射と呼ばれる自己射 idx = 1x: x → x が存在して、任意の射 f: a → x および g: x → b に対して 1x ∘ f = f and g ∘ 1x = g を満たす。
に出てくる =
は何?射は Equatable
なんでしょうか? =
が満たされる条件は何?始域と終域が同じであること?(つまり対象は Equatable
?) (edited)=
を定義しないといけないのか。(T) -> T
な関数は複数考えられてしまうし、関数のオプジェクトが同一であることと考えると複数の恒等関数が作れてしまうからダメだし、挙動が同じなら =
が成り立つとかにしないといけない? (edited)これらの公理から、各対象に対して恒等射はただ一つ存在することが示せる。
これも、一つであることを示すには二つの射が同じものかどうかを判定できないといけないから、暗黙的に 射: Equatable
と仮定されている?Int
-> Int
の射が複数存在して、それらが区別されてもいいですよね?圏(category) とは,対象 (object) と射(arrow, morphism) の集まりで,以下の条件を満た すものです: (1) おのおのの射には始域 (domain) と呼ばれる対象と終域 (codomain) と呼ばれる対象が定まっています.始域がaで終域がbである射f をf : a → bあるいはa−→b と書きます.た だし,a から b への射は一つとは限りません.また,射の始域と終域が同じ対象でもかまいません.
(edited)=
が使われているので射に対して =
を定義しないといけないと思うんですが、型と関数の圏を考えるときにどう考えるのが一般的なのかなと。func f(_ foo: Foo) -> Bar { ... } func g(_ bar: Bar) -> Baz { ... } { g(f($0)) } // g◦f
(edited)func foo(_ x: UInt) -> UInt { return x * x } func square(of number: UInt) -> UInt { let result = number * number return result } func bar(_ x: UInt) -> UInt { guard x > 0 else { return 1 } var result = 0 for v in 0..<x { result += x } return x }
{ g(f($0)) } // g◦f
foo(_)
と square(of:)
と bar(_)
を同一とみなす、ただし↓は同一とみなさないという場合です。 func qux(_ x: UInt) -> UInt { return x + x }
Equatable
を満たす型のみ)を対象とし、関数を射とします(引数の型が始域、戻り値の型が終域)。二つの関数 f: (X) -> Y, g: (X) -> Y があり、任意の x: X について関数 f(x) == g(x) が成り立つとき、 f と g は等しいものとします。このとき、任意の射 f1: (X) -> Y, f2: (Y) -> Z に対して f12: (X) -> Z = f2(f1(X)) が存在し、結合律、単位律が成り立つ(つまり、このような対象と射の集まりは圏な)のではないでしょうか?Foo.Type
は Equatable
じゃないといけないけど、 Foo
は Equatable
じゃなくていいみたいな。 typealias A = IntegerQuotientRing<_5> // 5 は素数 let a = A(4) let b = A(3) print(a / b) // 割り算ができる typealias A = IntegerQuotientRing<_4> // 4 は素数でない! let a = A(4) let b = A(3) print(a / b) // 割り算ができないのでちゃんとエラー
(edited)public struct _4 : _Int { public static let intValue = 4 } public struct _5 : _Prime { public static let intValue = 5 }
のように直接定義していますw (edited)// K1 = 𝐐[x]/(x^2 - 2) = 𝐐(√2). struct p1: _IrreduciblePolynomial { // p1 = x^2 - 2 static let value = Polynomial<𝐐>(-2, 0, 1) } typealias I1 = PolynomialIdeal<p1> // I = (x^2 - 2) typealias K1 = QuotientRing<Polynomial<𝐐>, I1> // K = Q[x]/I K1.isField // true let a = Polynomial<𝐐>(0, 1).asQuotient(in: K1.self) // a = x mod I a * a == 2 // a = √2
(edited)import SwiftyMath typealias AlgebraicExtension<F, p: IrrPolynomialTP> = PolynomialQuotientRing<p> where p.CoeffRing == F typealias Q = RationalNumber typealias Qx = xPolynomial<Q> let x = Qx.indeterminate struct p1: IrrPolynomialTP { static let value = Qx(coeffs: -2, 0, 1) } typealias A = AlgebraicExtension<Q, p1> // A = Q[x]/p1 let α = A(x) print(α) print(α * α) print(α * α == 2) struct p2: IrrPolynomialTP { static let value = xPolynomial<Q>(coeffs: 1, 0, 1) } typealias B = AlgebraicExtension<Q, p2> // B = Q[x]/p2 let i = B(x) print(i) print(i * i) print(i * i == -1)
SwiftyMath
をビルド対象から外してしまいました。 4.2は、オプション無しでインポート可能だけど、0.3.0とかのままですね。 @swift-4.2.4
import SwiftyMath
https://github.com/norio-nomura/SwiftCompilerDiscordappBot/blob/swift42/Libraries/Package%40swift-4.2.swift#L34