閉包
Windymelt(めるくん)🚀❤️🔥さんと他1000人
@windymelt
@Kory__3 @RayStark77 横からすみません、閉包について理解を確かめたいのですが、foo閉包とはfoo関係になっていない集合がfoo関係になるように要素を最低限補った集合、という認識でよいですか(半群の単位的(？)閉包に適宜lawを入れたものがモノイドである、という感じ？)
2024-02-12 00:26:58
Kory
@Kory__3
@windymelt @RayStark77 えーと、大体そうです ただし、「foo」になんでも入れられるわけでは無い (例えば、反射・対称・推移の三つの順序に関する性質は、後述する性質を共通して持っているから○○閉包が作れます) のと、半群からモノイドを作る操作とは少し作業するレイヤーが異なります。
2024-02-12 01:27:02
Kory
@Kory__3
@windymelt 集合 X 上の二項関係 R (: Set[(X, X)]) を固定します。 まずは R の反射閉包の事を考えたいので、P := { S: Set[(X, X)] | R subsetOf S } (「R を含む X 上の反射関係」の集まり) だとします。 この時、 P は nonEmpty です (X × X という ("どの二要素に対しても成り立つ") 関係が P の要素)。
2024-02-12 01:53:23
Kory
@Kory__3
@windymelt P の全要素の交差 ∩P、つまり P.flatten.filter(pair => P.forall(_ contains pair)) も反射的です (任意の x: X について、 P のどの要素も反射的で、つまり (x, x) を含んでいるので、 ∩P にも (x, x) が含まれている)。 なので、∩P が「X を含む最小の反射関係」であり、反射閉包と呼びます。
2024-02-12 01:56:26
Kory
@Kory__3
@windymelt 対称閉包や推移閉包も似たように定義でき、「元の関係を含む最小の対称/推移関係」として定義されています。 …というわけで、認識としては「要素を最低限補った集合」で良いです。ところで、「どう最低限補えばよいのか」というのがちょい非自明です。
2024-02-12 02:26:59
Kory
@Kory__3
@windymelt 「R を含む最小の…」という形の定義はこの観点では非常に非効率的です。例えば対角線上の組たち ((1,1), (2,2), ... みたいな形をした組) を全部 R に加えてやるだけで反射閉包 、「R を含む最小の…」という定義だと、R を含む関係すべて (!) を取ってきて、
2024-02-12 02:27:08
Kory
@Kory__3
@windymelt この「X を含む foo な順序を全部取ってきて共通部分を取る」操作による定義は、「X を含む foo な順序が存在する」と「foo な順序の集まりの共通部分はやはり foo」という foo に関する (foo が反射・対称・推移のいずれかならば成り立つ) 二つの性質にしか依存しない便利定義なんですが、
2024-02-12 02:43:00
Kory
@Kory__3
@windymelt 計算するときには、foo が何であるかに依存したもっとマシな方法 (反射閉包なら (x, x) の形のものを全部足す、対称閉包なら各 (x, y) ∈ R について (y, x) を放り込む、推移閉包なら…ちょいめんどい…) で計算しがちです (一般性は減りますが、各々の具体的な計算方法を定義とすることもあります)
2024-02-12 02:45:26
Kory
@Kory__3
@windymelt 結局、「foo閉包はfooになるように最低限 (要素ではなく、成り立つ) 関係を補ったもの」ではあるんですが、最低限補う is 何？というところを突き詰めると、一般的だが計算に向かない定義と、それを楽に計算できるようにしたものの二通りが表れるという感じです (話が長くなっちゃった…)
2024-02-12 02:49:02
Kory
@Kory__3
@windymelt 最初に「半群からモノイドを作る操作とはレイヤーが異なる」といっていたのは、閉包を取る操作は「X という台集合は固定されたままの状況で成り立つ関係性を継ぎ足す」のに対し、半群からモノイドを作ったりするときは「そもそも台集合を最小限拡張して無理やりモノイドにする」からですね
2024-02-12 02:50:32
Kory
@Kory__3
@windymelt これら二つの操作は左随伴という概念で同じようなものだと捉えられる (…と思います、閉包を取る操作が左随伴なのかについて確信が無い)、その話は長くなりそうなのでまた今度で…
2024-02-12 02:52:09
Windymelt(めるくん)🚀❤️🔥さんと他1000人
@windymelt
@Kory__3 どうもありがとうございます、よく読んでみます :bow: :bow:
2024-02-12 02:59:47文脈
In addition to the answers already given, here's a link to an article I think is relevant. Excerpts:
In the object-oriented framework, inheritance is usually presented as a feature that goes hand in hand with subtyping when one organizes abstract datatypes in a hierarchy of classes. However, the two are orthogonal ideas.
Subtyping refers to compatibility of interfaces. A type B is a subtype of A if every function that can be invoked on an object of type A can also be invoked on an object of type B.
Inheritance refers to reuse of implementations. A type B inherits from another type A if some functions for B are written in terms of functions of A.
However, subtyping and inheritance need not go hand in hand. Consider the data structure deque, a double-ended queue. A deque supports insertion and deletion at both ends, so it has four functions insert-front, delete-front, insert-rear and delete-rear. If we use just insert-rear and delete-front we get a normal queue. On the other hand, if we use just insert-front and delete-front, we get a stack. In other words, we can implement queues and stacks in terms of deques, so as datatypes, Stack and Queue inherit from Deque. On the other hand, neither Stack nor Queue are subtypes of Deque since they do not support all the functions provided by Deque. In fact, in this case, Deque is a subtype of both Stack and Queue!
I think that Java, C++, C# and their ilk have contributed to the confusion, as already noted, by the fact that they consolidate both ideas into a single class hierarchy. However, I think the example given above does justice to the ideas in a rather language-agnostic way. I'm sure others can give more examples.
(deepl)すでに与えられた答えに加えて、ここに関連すると思われる記事へのリンクを掲載する。抜粋します：
オブジェクト指向のフレームワークでは、継承は通常、抽象的なデータ型をクラスの階層にまとめるときに、サブタイプ化と密接に関連する機能として提示される。しかし、この2つは直交する考え方です。
サブタイピングとは、インターフェースの互換性のことである。A型のオブジェクトに対して呼び出すことができるすべての関数が、B型のオブジェクトに対しても呼び出すことができる場合、B型はA型のサブタイプである。
継承とは、実装の再利用のことである。B型の関数がA型の関数で記述されている場合、B型はA型を継承する。
しかし、サブタイピングと継承は両立する必要はない。データ構造deque（両端待ち行列）を考えてみよう。dequeは両端での挿入と削除をサポートするため、insert-front、delete-front、insert-rear、delete-rearの4つの関数を持つ。insert-rearとdelete-frontだけを使えば、通常のキューになる。一方、insert-frontとdelete-frontだけを使えば、スタックになる。つまり、キューとスタックをDequeで実装することができ、データ型としてはStackとQueueはDequeを継承する。一方、スタックもキューも、Dequeが提供するすべての関数をサポートしているわけではないので、Dequeのサブタイプではない。この場合、DequeはStackとQueueの両方のサブタイプということになる！
Java、C++、C#とその一派は、すでに述べたように、両方の考え方を単一のクラス階層に集約していることが、混乱を助長していると思う。しかし、上に挙げた例は、言語にとらわれない方法で、この考え方を正しく表していると思う。他の人ならもっと多くの例を挙げることができるだろう。
Kory
@Kory__3
@RayStark77 この回答に言いたいことが9割書いてあるんですが、いくつか付け加えておきます (回答の方を先に読むことをお勧めします)
2024-02-11 23:46:29
Kory
@Kory__3
@RayStark77 まず、Java からジェネリクス関連をすべて抜いたくらいの言語では「subtyping 関係 (<:) は継承関係の反射閉包と一致する」程度の事は言えそうです。この時点で概念上の乖離は起こっており、例えば class が自分自身を extends することは無いですが、部分型付け関係は反射的 (常に C <: C) です。
2024-02-11 23:47:17
Kory
@Kory__3
@RayStark77 ジェネリクスが入るだけで一気に二つの概念の乖離が大きくなり、例えば List<String> <: List<? extends String> <: List<? extends Object> ですが、 - List<String> は List<? extends String> を - List<? extends String> <: List<? extends Object> を それぞれ「継承」はしていません。 (続)
2024-02-11 23:47:59
Kory
@Kory__3
@RayStark77 これら関係性は、「型コンストラクタ T<_> と型 S1, S2 について、S1 <: S2 ならば T<S1> <: T<? extends S2>」や「S1 <: S2 ならば T<? extends S1> <: T<? extends S2>」といった形の、言語 (今回は Java) 内で部分型付けとはいかなる関係なのかという定義に従って機械的に判定されるものです。 (続)
2024-02-11 23:52:36
Kory
@Kory__3
@RayStark77 Java の話から離れてしまえば、別に「部分型付けとは型の間のいかなる関係なのか」が「クラス間の継承関係」とはかけ離れたところに生えて*いても良い*という話になってきます。
2024-02-12 00:00:51
Kory
@Kory__3
@RayStark77 継承関係がひとつも無い言語が部分型付け関係を規定しても良い (例:「偶数であることがチェックされた Int をわざわざクラスに包まずに Int の真のサブクラスとして扱う」(篩型)) ですし、継承があるにも関わらずsubtyping 関係が無くても (例えば型無しの動的言語ではそうですよね) 良いわけです。
2024-02-12 00:01:12
Kory
@Kory__3
@RayStark77 そういう意味でも、上で貼った stackoverflow の回答が言う通り、「subtyping と継承はやりたいことが違う」んですよね (終)
2024-02-12 00:03:27
RayStark a.k.a. ロジニキ
@RayStark77
@Kory__3 このように理解したんですけどコリーさんの認識と合っていますか？ x.com/RayStark77/sta…
2024-02-12 00:09:15
RayStark a.k.a. ロジニキ
@RayStark77
inheritance := reuse of implementationsとした上で - inheritanceとsubtypingは同一ではないよ - subtypingによってinheritanceを実現する事が問題だよ っていう事か、なるほど。
2024-02-11 23:53:07
RayStark a.k.a. ロジニキ
@RayStark77
inheritance := reuse of implementationsとした上で - inheritanceとsubtypingは同一ではないよ - subtypingによってinheritanceを実現する事が問題だよ っていう事か、なるほど。
2024-02-11 23:53:07
Kory
@Kory__3
@RayStark77 3 行目だけ認識が合ってないかもです (当ツリーではそのような主張はしていないのと、僕は継承関係が subtype 関係の一部になっているのはむしろ筋が良いと思っています)
2024-02-12 00:13:13
RayStark a.k.a. ロジニキ
@RayStark77
@Kory__3 確かに。読み違えてしまってごめんなさい。理解が深まりました。ありがとうございます。
2024-02-12 00:16:19