想了解TreeStructure和Recursion的新动态吗？本文将为您提供详细的信息，此外，我们还将为您介绍关于AFastWait-FreeSimulationforLock-FreeDataSt

想了解Tree Structure 和Recursion的新动态吗？本文将为您提供详细的信息，此外，我们还将为您介绍关于A Fast Wait-Free Simulation for Lock-Free Data Structures、Category Theory: 01 One Structured Family of Structures、com.intellij.ui.treeStructure.actions.ExpandAllAction的实例源码、com.intellij.ui.treeStructure.AlwaysExpandedTree的实例源码的新知识。

• Tree Structure 和Recursion
• A Fast Wait-Free Simulation for Lock-Free Data Structures
• Category Theory: 01 One Structured Family of Structures
• com.intellij.ui.treeStructure.actions.ExpandAllAction的实例源码
• com.intellij.ui.treeStructure.AlwaysExpandedTree的实例源码

Tree Structure 和Recursion

使用 PostgreSQL 8.4.14 数据库，我有一个表示树结构的表，如下例所示：

CREATE TABLE unit (    id bigint NOT NULL PRIMARY KEY,    name varchar(64) NOT NULL,    parent_id bigint,    FOREIGN KEY (parent_id) REFERENCES unit (id));INSERT INTO unit VALUES (1, ''parent'', NULL), (2, ''child'', 1)                      , (3, ''grandchild A'', 2), (4, ''grandchild B'', 2); id |    name      | parent_id ----+--------------+-----------  1 | parent       |            2 | child        |         1  3 | grandchild A |         2  4 | grandchild B |         2

我想为这些单元创建一个访问控制列表，其中每个单元可能有自己的 ACL，或者从最近的祖先那里继承它并拥有自己的 ACL。

CREATE TABLE acl (    unit_id bigint NOT NULL PRIMARY KEY,    FOREIGN KEY (unit_id) REFERENCES unit (id));INSERT INTO acl VALUES (1), (4); unit_id ---------       1       4

我正在使用视图来确定一个单元是否从祖先那里继承了它的 ACL：

CREATE VIEW inheriting_acl AS    SELECT u.id AS unit_id, COUNT(a.*) = 0 AS inheriting    FROM unit AS u    LEFT JOIN acl AS a ON a.unit_id = u.id    GROUP BY u.id; unit_id | inheriting ---------+------------       1 | f       2 | t       3 | t       4 | f

我的问题是：我怎样才能获得不从祖先那里继承 ACL的最近单元？我的预期结果应该类似于下表/视图：

 unit_id | acl ---------+------------       1 | 1       2 | 1       3 | 1       4 | 4

答案1

具有递归 CTE 的查询可以完成这项工作。需要 PostgreSQL 8.4或更高版本：

WITH RECURSIVE next_in_line AS (    SELECT u.id AS unit_id, u.parent_id, a.unit_id AS acl    FROM   unit u    LEFT   JOIN acl a ON a.unit_id = u.id    UNION  ALL    SELECT n.unit_id, u.parent_id, a.unit_id    FROM   next_in_line n    JOIN   unit u ON u.id = n.parent_id AND n.acl IS NULL    LEFT   JOIN acl a ON a.unit_id = u.id    )SELECT unit_id, aclFROM   next_in_lineWHERE  acl IS NOT NULLORDER  BY unit_id

第二回合的休息条件UNION是n.acl IS NULL。这样，一旦acl找到，查询就会停止遍历树。
最后，SELECT我们只返回acl找到an 的行。瞧。

顺便说一句：使用通用的、非描述性的id作为列名是一种反模式。可悲的是，一些 ORM 默认情况下会这样做。调用它unit_id，您不必一直在查询中使用别名。

A Fast Wait-Free Simulation for Lock-Free Data Structures

基于CAS(compare-and-swap)操作的无锁算法，几乎都可以采用《无锁算法的无等待模拟》来转化为无等待算法，从而获得更强的progress。
相对于《无锁算法的无等待模拟》中的算法所采用的类似无等待队列，本文换成一种基于getAndAdd+CAS的无等待队列。
本文我用自己的方式来介绍下：

1. 如何从一个基于CAS的正确(一致性)的无锁算法转化为无等待算法，针对CAS操作建模（无等待算法）
2. 同时基于环形的线程专属数据环，由于依赖于具体的数据偏移，降低了公平性。所以使用一种更快速的类似wait-free队列，从而获得更好的公平性。

几乎所有的无锁算法(先不考虑垃圾回收)，对于一个线程而言，都是一个如下的过程：

要么成功(本操作make progress)、要么失败(其他线程的操作make progress)从而本操作需要更新数据(preCasOp)，再次重复直到成功。并且最后要执行必要的postCasOp。

那么，对于一个value，我们将它置于一个record里：

struct Record {
    void* value;
};
struct Record* Head; 

算法的关键在于，对一个head的原子改变：

lock-free-method(void* value) {
    for(;;) {
        before;
        Record* head = Head;
        Record* myRecord = Generate(head, value);
        if(CAS(&Head, head, myRecord)) {
            after;
            return;
        }
    }
}

这里的问题在于，对于一个操作lock-free-method(val)，它在这一行CAS(&Head, head, myRecord)，我们需要在这一行取得成功才能算本操作make progress。但是我们无法确定什么时候能够取得成功。在操作系统内核的调度算法越来越好的情况下，我们很可能绝大多数情况下不会感受到某次操作的延迟。但是有没有办法能够确保，本操作能够在有限步之后完成。这种算法性质就叫做wait-freedom。
我们转化成的wait-free算法具有如下结构：

• 每个线程都先在fast-path中尝试MAX-fast次，假如某次成功则返回，假如成功的次数达到ENOUTH-fast(per thread)，那么就通过shareMemory协助处于slow-path中的操作一次。
• 假如fast-path中尝试MAX-fast次仍未成功，则构造自己的请求信息放到shareMemroy，接着进入slow-path。
• 进入slow-path的线程，不断地尝试，最终会在有限次尝试内，自己完成操作，或者由其他线程帮助完成。

• 协助过程，可以抽象出取得一致性的三个接口：

  HELP(handle) HELP_TRANSFER(head) HELP_TRANSFER_VALUE(head, handle)
  

对于如上这个具体操作，我们可以做如下操作：
首先，给Record结构增加一个Handle_t数据类型：

typedef struct Record {
    void* value;
    Handle_t* handle;
} Record;
typedef struct Handle_t {
    void* value;
    struct Wrapper* wrapper;
} Handle_t;
typedef struct Wrapper {
    bool isFinish;
    Record* record;
} Wrapper;

我们把lock-free-method进行改造：

• 原来的lock-free-method作为fast-path，给定两个阈值，MAX1：让它执行够次数就退出。构造原来的请求，放入共享内存中(可以是并发队列)。 MAX2: 在fast-path中执行成功的次数，从而主动help slow-path中的请求
• CAS操作不再像原来一样在在value的值上改变，而是根据record->handle是否为空来继续操作：为空则尝试自己的请求，不为空则尝试帮助handle对应的请求make progress。(同理，fast-path也进行修改。）
• handle中会有个指向Record的指针，以及代表本操作是否完成的bit和version。

所以，slow-path通过引入两个中间状态(states)，把本来一个CAS操作变为了三个CAS操作：

• STEP 1: (exclusive)线程A尝试把原来的Record，指向请求所对应的Handle，make progress(state 1，该Record被某个线程锚定).
• STEP 2: (consisent)某个线程B(B为任意线程)从Record中取出Handle，并且将该Handle指向这个Record，同时设置finish bit，从而告知该次请求完成，make progress.(state 2，说明此事操作已经完成)
• STEP 3: 线程A从自己的handle中获知操作已完成(finish bit，stete 2导致的)，并且获取自己锚定的Record，更新Record的值，从而完成收尾工作，并且返回自己的操作结果(state 3，此时Record的值又回到了原来的状态，与lock-free中的结果一致)

伪代码如下：

wait-free-method(void* value) {
    // fast-path
    for(int i = MAX1; i--;) {
        before;
        Record* head = Head;
        if(head->handle == NULL) {
            Record* myRecord = NewValueRecord(head, value);
            if(CAS(&Head, head, myRecord)) {
                after;
                if((--meHandle->fastTimes) == 0) {
                    meHandle->fastTimes = MAX2;
                    Handle_t* handle = peekOneHandle(shareMemory);
                    if(handle != NULL)
                        HELP(handle);
                }
                return;
            }
        } else {
            // help the Record head
            HELP_TRANSFER(head);
        }
    }
    // construct myself request into shareMemory
    meHandle->value = value;
    meHandle->wrapper->isFinish= false;
    meHandle->wrapper->record = NULL;
    putMeHandleIn(shareMemory, meHandle);
    // slow-path
    HELP(meHandle);
    while(there is handle in shareMemory before meHandle)
        HELP(handle);
}

HELP(Handle_t* handle) {
    before;
    Record* head = Head;
    while(!handle->wrapper->isFinish) {
        // Record* head = Head; 这一行应该在测试isFinish之前
        if(head->handle == NULL) {
            Record* myRecord = NewHandleRecord(head, handle);
            if(!CAS(&Head, head, myRecord)) {
                head = Head;
                continue;
            }
            head = myRecord;
        }
        // help the Record head
        HELP_TRANSFER(head);
        before;
        head = Head;
    }
    head = handle->wrapper->record;
    HELP_TRANSFER_VALUE(head, handle);
}

HELP_TRANSFER(Record* head) {
    Handle_t* handle = head->handle;
    finishHandle(shareMemory, handle);
    Wrapper* wrapper = handle->wrapper;
    if(!wrapper->isFinish) {
        //transfer to state 2.
        Wrapper* newWrapper = NewWrapper(head, true);
        CAS(&handle->wrapper, wrapper, newWrapper);
    }
    HELP_TRANSFER_VALUE(head, handle);
}

HELP_TRANSFER_VALUE(Record* head, Handle_t* handle) {
    if(Head == head) {
        //transfer to state 3.
        Record* myRecord = NewValueRecord(head, handle->value);
        if(CAS(&Head, head, myRecord))
            after;
    }
}

简化一下，如下伪代码：

wait-free-method(void* value) {
    // fast-path
    for(int i = MAX1; i--;) {
        .......
        if(!there is a requestHandle in Record) {
            if(try myRequest) {
                if(successTimes is enough) {
                    helpOneRecordInShareMemory();
                }
                return;
            }
        } else {
            helpTheRecord();
        }
    }
    // construct my request handle(value/Wrapper(Record*:NULL, isFinish:false));
    construct myself request into shareMemory
    // slow-path
    while(my request is not finish) {
        if(!there is a request in Record) {
            if(!try myRequest) 
                continue;
            assert(there is a request in Record: myRequest);
        }
        helpTheRecordFinish();
    }
    helpTheRecordFinishValue();
}

这里面的shareMemory，强烈建议改造链接描述中的队列来使用，这里需要的是个类似队列的数据结构。
从而达到对于shareMemory的操作也是无等待的，从而保证了整个算法最强的wait-freedom。

Category Theory: 01 One Structured Family of Structures

Category Theory: 01 One Structured Family of Structures

这次看来要放弃了。看了大概三分之一。似乎不能够让注意力集中了。先更新吧。

群的定义

$G = {G, +, e}$，一个数据集 $G$，一个二元操作符 $+$，和一个幺元 $e$。

满足结合律：$(a + b) + c = a + (b + c)$ 满足封闭性。 存在单位元：$e + a = a = a + e$ 存在逆元：对于每一个 a，存在一个逆元 a'': $a + a'' = e$ 如果满足交换律，则是一个交换群，也就是阿尔贝群。

群的同态 (homomorphism) 和同构 (isomorphism)

• 定义：同态 (homomorphism) 群同态是一个函数 f，应用于源群 $(G, *, e)$ 和目标群 $(G'', *'', e'')$，满足：

  1. $f(x * y) = f(x) *'' f(y)$
  2. $f(e) = e''$ e.g. $f(x) = e^x, e^{x + y} = e^x e^y$

• 定理：

  1. 群 $(G, *, e)$，总有一个单位同态，$1_G : G \to G$.
  2. 给定两个同态 $f: G \to H, g: H \to J$，存在一个组合同态 $g \circ f : G \to J$.
  3. 同态的组合满足结合律 (associative)，$j \circ (g \circ f) = (j \circ g) \circ f$

• 定义：同构 (isomorphism) 群同构 $(f : G \simeq H)$ 是一个同态，如果其对应的函数是一个双射。

• 定理： 一个群同态 $f: G \to H$ 是一个同构，当且仅当它有一个双边的逆，也就是说，有一个同态 $f'': H \to G$，有 $f'' \circ f = 1_G, f \circ f'' = 1_H$。

• 定理 在群之间的同构是一个群之间的等价关系。

02 范畴的定义

一个范畴是一个带标签的有向图，其节点为对象 (object)，带有标签的有向边为箭头 (arrow or morphism)。

一个范畴 C 包含 2 个数学实体：

• 对象集合：ob (C) 每个元素都是一个对象，一个对象又可以认为是一个集合。

• 态射集合: hom (C) 态射集合的每个元素是一个态射，$f: a \to b$，每个态射 f 有一个源对象 (source object) a 和目标对象 (target object) b。 $hom (a, b)$ 表示从 a 到 b 的所有态射。 每个态射 $f: A \to B$ 有 src () 和 tgt ()，两个属性，可以获得源对象和目标对象，i.e. $A = src (f), B = tgt (f)$。

• 性质：

  • 二元操作：态射结合 (composition of morphisms): $\circ$ $f: a \to b, g: b \to c$ 的结合是 $g \circ f$。

• 公理

  • 满足结合律 (Associativity): $ h \circ ( g \circ f ) = ( h \circ g ) \circ f $ 结合律意味着操作执行的次序不影响其总体结果，是等价的。但是操作元素的次序不能改变（不满足交换律）。
  • 存在恒等态射 (identity): 对于每个对象 x，存在一个恒等态射 (identity morphism) $1_x: x \to x$， 其性质为，对于任何态射 $f: a \to b$，有 $1_b \circ f = f = f \circ 1_a$ 恒等态射的含义是：定义了相同关系 (equality relation A = B)。 可以简单的认为是；$f (x) = x$。

• 定理：一个对象的单位箭头是唯一的；不同对象的单位箭头是不同的。

范畴的理解

• 对象 从编程语言的角度来说，一个类（范畴）并不需要一个对象集合。 一个类的对象集合是由这个类的属性和方法决定的，是编程语言的各种数据类型和类的各种各样的组合形式。 我们往往用元类型来描述范畴里的对象。

• 态射 态射就是一个类的方法。 一个方法有多个输入或者输出，可以简单地认为其源对象或者目标对象是一个对象组合。 如何理解一个没有输入的静态方法。

态射的种类

单态射 (monomorphism) $\simeq$ 单射 (injective) 满态射 (epimorphism) $\simeq$ 满射 (surjective) 双态射 (bimorphism) = 单态射 (monomorphism) + 满态射 (epimorphism) 同构 (isomorphism) = 双态射 (bimorphism) + 存在逆态射 自态射 (endomorphism) = (src (f) = tgt (f)) 自同构 (automorphism) = 自态射 (endomorphism) + 同构 (isomorphism) 撤回射 (retraction) = 存在右逆 部分射 (section) = 存在左逆 同态 = 两个数据结构之间满足分配律。$f (x * y) = f (x) *'' f (y)$

半幺群和预次序集合

• 幺半群 (monoid) 没有逆元限制的群。 $(M, \dot, e_M)$，$\dot$ 是一个二元函数，$e_M$ 是一个显著对象。

  1. $\dot$ 是满足结合律：$(a \dot b) \dot c = a \dot (b \dot c), \forall a, b, c \in M$
  2. $e_M \dot a = a = a \dot e_M$ 例如：$(\mathbb {N}, +, 0)$ 是一个幺半群。

• 预次序集合 (pre-ordered collection) $(M, \leqslant)$，具有:

  1. $a \leqslant b, b \leqslant c \implies a \leqslant c$,
  2. $a \leqslant a$

• 单调映射 (monotone map) 作用于次序集合上的单调映射 $f: (M, \leqslant) \to (N, \sqsubseteq)$，具有：如果 $a \leqslant b, \forall a, b \in M$, 则 $f (a) \sqsubseteq f (b)$。

范畴的例子

• Mon Mon 是对象为所有幺半群，箭头为幺半群同态。

• Ord Ord 是对象为所有预序组，箭头为他们之间的单调映射。

• Set Set 是对象为所有 set，箭头为他们之间的任意集合函数。

• Grp Grp 是对象为所有 group，箭头为 group 的同态。

• Ab Ab 是对象为所有 abelian group，箭头为 group 的同态。

• Rng Rng 是对象为所有 ring，箭头为 ring 的同态。

• 任取一个幺半群 $(M, \dot, e_M)$，定义范畴 $\mathcal {M}$ 如下：

  1. $\mathcal {M}$ 的唯一的对象是任何实体（不一定是 M 中的对象），我们称其为 $\star$
  2. $\mathcal {M}$ 的箭头 $a : \star \to \star$ 就是幺半群中的一个对象 a；
  3. 箭头的组合 $a \circ b$ 定义为幺半群对象的积 $a \dot b$；
  4. 单位箭头 1 定义为幺半群的单位元 $e_M$。

4: 范畴生范畴

• 对偶 (duality) 对于一个范畴 $\mathcal {C}$ 的对偶 (dual)$\mathcal {C}^{op}$，也称为逆范畴、反向范畴 (opposite)。满足：

  1. $ob(\mathcal{C}^{op}) = ob(\mathcal{C})$
  2. 对于 $\mathcal {C}, f : A \to B$，存在 $\mathcal {C}^{op}， f : B \to $
  3. 单位箭头保持不变: $1_A^{op} = 1_A$
  4. $\mathcal {C}^{op}$ 的复合定义： $f \circ^{op} g = g \circ f$

• 子范畴 (subcategory) $\mathcal {C}$ subcategory $\mathcal {S}$：

  1. objects: some or all of the $ob(C)$,
  2. arrows: some or all of the $hom(C)$,
  3. for each $o \in ob(S)$, the arrow $1_o \in hom(S)$
  4. for any arrow $f: C \in D, g: D \to E$, the arrow $g \circ f: C \to E \in hom(S)$

• 全子范畴 (full subcategory) $\mathcal {C}$ subcategory $\mathcal {S}$ is a full subcategory, when： $\forall A, B \in ob (S), hom_S (A, B) = hom_C (A, B)$

• 积范畴 (product category)

• 等价关系 (congruence relation)

• 商范畴 (quotient category) 商范畴 $\mathcal {C}/\sim = （ob (C), hom (hom (X \to Y）\to \sim class)$ 是对一个范畴，按照某种属性进行分类。 商范畴的态射，我的理解是：C 的态射 -> 一个具体的分类属性。 还有一个理解是：$A \to B, A \sim B$ 一个例子： If X is the set of all cars, and ~ is the equivalence relation "has the same color as", then one particular equivalence class consists of all green cars. X/~ could be naturally identified with the set of all car colors.

• 箭范畴 (Arrow categories) 一个范畴 $\mathcal {C}$ 的派生箭范畴 $\mathcal {C}^{\to}$， $ob (C)$ 是范畴 $\mathcal {C}$ 的所有箭头 $hom (C)$。 给定一个 $\mathcal {C}^{\to}$ 的对象 $f_1, f_2 | f_1 : X_1 \to Y_1, f_2 : X_2 \to Y_2$， 可以派生一个 $\mathcal {C}^{\to}$ 的箭头 $f_1 \to f_2$ 是一个匹配 $(j, k) | j : X_1 \to Y_1, K : X_2 \to Y_2 \in hom (C)$,

• 切片范畴 (Slice categories) 一个范畴 $\mathcal {C}$ 的派生切片范畴 $\mathcal {C}/I, I \in ob (C)$, $(A, f) \in ob (C/I) | A \in ob (C), f : A \to I \in hom (C)$, $j'' : (A, f) \to (B, g) \in hom (C/I) | j : A \to B, g \circ j = f, j \in hom (C)$, $1_{(A, f)} = 1_A : A \to A | 1_A \in hom (C)$ $j : (A, f) \to (B, g), k : (B, g) \to (C, h), k \circ j : (A, f) \to (C, h) | k \circ j \in hom (C)$

5: Kinds of arrows

Monomorphism vs Injective

• definition: monomorphism An arrow $f : C\to D$ in the category $\mathcal {C}$ is a monomorphism (monic) if and only if it is left-cancellable.. left-cancellable - 左可消除。 i.e. for $g : B \to C$ and $h : B \to C$, if $f \circ g = f \circ h \implies g = h$

• Theorem : the monomorphisms in Set are exactly the injective functions 意味着不是所有的范畴的单射都是单射方法。

• Theorem : the monomorphisms in Grp are exactly the injective group homomorphisms

Epimorphism vs Surjective

• definition: epimorphism An arrow $f : C\to D$ in the category $\mathcal {C}$ is a epimorphism (epic) if and only if it is right-cancellable.. right-cancellable - 右可消除。 i.e. for $g : B \to C$ and $h : B \to C$, if $g \circ f = h \circ f \implies g = h$

• Theorem : the epimorphisms in Set are exactly the surjective functions 意味着不是所有的范畴的满射都是满射方法。

• Theorem : the epimorphisms in Grp are exactly the surjective group epimorphisms

• Theorem :

  1. 单位箭头总是单射，并且也是满射。
  2. 如果 f, g 是单射，$f \circ g$ 也是单射。
  3. 如果 f, g 是满射，$f \circ g$ 也是满射。
  4. 如果 $f \circ g$ 也是单射，则 g 是单射。
  5. 如果 $f \circ g$ 也是满射，则 f 是满射。

逆态射 (Inverses)

• 定义：在范畴 $\mathcal {C}$ 中给定一个箭头 $f : C \to D$,
  1. $g： D \to C$ 是 f 的一个 right inverse，$\iff f \circ g = 1_D$.
  2. $g： D \to C$ 是 f 的一个 left inverse，$\iff f \circ g = 1_C$.
  3. $g： D \to C$ 是 f 的一个逆，如果 g 是 f 的左逆和右逆.

right 和 left 只是一个记号，没有方向性的含义。 可以这样想象：$C \to D$ C 在左边，D 在右边。 右逆：是从 D 出发，逆回到 D，$f \circ g = 1_D$； 左逆：是从 C 出发，逆回到 C，$g \circ f = 1_C$;

• 定理：如果一个箭头有左逆和右逆，那么左逆和右逆是同一个，也是原箭头的逆。 $r = 1_C \circ r = (s \circ f) \circ r = s \circ (f \circ r) = s \circ 1_D = s$

• 定理：

  1. 通常，不是每一个单态射都是右逆；（可能存在元素 $c | c \in C$ 在 D 中没有对应的元素。）
  2. 同样，不是每一个满态射都是左逆。（可能存在元素 $d_1, d_2 | d_1, d_2 \in D$ 同时指向 $c | c \in C$。）
  3. 但是，每一个右逆都是单态射，每一个左逆都是满态射。

• 定理： 在 Set 中，每一个单态射是一个右逆，除了 $\emptyset \to D$。 同理，在 Set 中，推论 “每一个满态射是一个左逆” 是一个选择公理 (Axiom of Choice) 的一个版本。

• 定义：section and retraction 如果 $g \circ f = 1_C$，f 也称为是 g 的一个部分态射 (section)；g 称为是 f 的一个撤回态射 (retraction)。

• 定义：split monomorphism and split spimonomorphism 如果 f 有一个左逆，那么 f 是一个拆分单态射； 如果 g 有一个右逆，那么 g 是一个拆分满态射。

同构 (Isomorphisms)

• 同构 (isomorphism) 在范畴里的一个同构是一个有逆箭头。一般用 $\sim \over \longrightarrow$。

• 定理

  1. 单位箭头是同构。
  2. 一个同构 $f: C \sim \over \longrightarrow D$，有一个唯一的逆，记为 $f^{-1} : D \sim \over \longrightarrow C$，存在以下性质：
  • $f^{-1} \circ f = 1_C$
  • $f \circ f^{-1} = 1_D$
  • (f^{-1})^{-1} = f
  • f^{-1} 是一个同构
  1. 如果 f 和 g 是同构，那么如果 $g \circ f$ 如果存在，也是一个同构。它的逆是 $f^{-1} \circ g^{-1}$。 比如：双射是一个同构。

• 定理 如果 f 同时是单态射 (monic) 和拆分满态射 (split epic)(或者同时是满态射 (epic) 和拆分单态射)，那么 f 是一个同构。

• 定理 15 如果 f 和 g 是具有相同目标对象的单态射箭头。并且存在 i,j，有 $f = g \circ i, g = f \circ j$，那么因子 i 和 j 是同构态射，并且互为逆。

• 定义：平衡的 (balanced) 范畴 $\mathcal {C}$ 是平衡的，当且仅当每一个箭头都是一个同构。

同构的对象 (Isomorphic objects)

• 定义：同构的对象 (Isomorphic objects) 在范畴 $\mathcal {C}$ 中，一个同构 $f : C \sim \over \longrightarrow D$，那么对象 $C, D$ 称为在范畴 $\mathcal {C}$ 中被同构化，记做 $fC \sim \over \longrightarrow D$。

• 定理 16 在范畴 $\mathcal {C}$ 中，一个对象之间的同构是一个等价关系。

• 定理 17 在范畴 $\mathcal {C}$ 中，如果 $f : C \sim \over \longrightarrow D$，那么对于所有的对象 $X \in \matchcal {C}$，在箭头 $C \to X$ 和箭头 $C \to \Y$ 之间有一对一的对应。同样，存在一对一的对应在箭头 $X \to C$ 和箭头 $Y \to C$ 之间。

6 起点和终点对象 (Initial and terminal objects)

• 定义：起点对象 (initial object) 在范畴 $\mathcal {C}$ 中，对象 $I$ 是起点对象，如果，对于每一个范畴中的对象 X，都有一个唯一的箭头 $! : I \to X$，可以记做 $!_x$。

• 定义：终点对象 (terminal object) 在范畴 $\mathcal {C}$ 中，对象 $T$ 是终点对象，如果，对于每一个范畴中的对象 X，都有一个唯一的箭头 $! : X \to T$，可以记做 $!_x$。

• 定义：空对象 (null object) 在范畴 $\mathcal {C}$ 中的空对象 $O$，如果，对于 $O$ 即是起点对象也是终点对象。

从唯一性到唯一性同构 (Uniqueness up to unique isomorphism)

• 定理：起点对象之间是 “从唯一性到唯一性同构”。 在范畴 $\mathcal {C}$ 中，$I, J$ 是起点对象，则存在一个唯一的同构 $f : I \sim \over \longrightarrow J$。 对终点对象，亦然。 如果 $I$ 是一个起点对象，有 $f : I \sim \over \longrightarrow J$，则 $J$ 也是一个起点对象。

• 定义：将起点对象记为 $0$，将终点对象记为 $1$

元素和通用化的元素 (Elements and generalized elements)

• 定义：元素 在一个带有终点对象 $1$ 范畴 $\mathcal {C}$ 中，对象 X 的一个元素 (或者对象 X 的一个点) 是一个箭头 $f: 1 \to X$。

• 定义: well-pointed 假设范畴 $\mathcal {C}$ 有一个终点对象，并且假设范畴 $\mathcal {C}$ 中的任意对象 $X, Y$，平行箭头 $f, g : X \to Y$，$f = g$ 如果 $f \circ x = g \circ x, \forall x : 1 \to X$，那么范畴 $\mathcal {C}$ 被称为 (well-pointed)。

• 定理：拿出两个终点对象 $1$ 和 $1''$，定义两个不同类型的 X 的元素 $f_1 : 1 \to X$ 和 $f_2 : 1'' \to X$。范畴 $\mathcal {C}$ 对于第一个元素是 well-pointed，当且仅当范畴 $\mathcal {C}$ 对于第二个元素也是 well-pointed。

• 定义：通用化的元素 (generalized elements) 在范畴 $\mathcal {C}$ 中，一个 $X$ 对象的（shape S 的）通用化元素 (generalized element) 是一个箭头 $e: S \to X$

• 定理：在范畴 $\mathcal {C}$ 中，平行箭头是相同的，当且仅当它们在所有的通用化元素上都是相同的。

• 定理：在范畴 $\mathcal {C}$ 中，点元素 $x: 1 \to X$ 都是单态射。

  每一个生命都是神圣不可侵犯的。 每一个生命都只是一粒尘埃。 我们既可以尊重每个生命，又可以对其随心所欲。就是这么矛盾。

7 乘积 (products)

结对模式

• 定义: pairing schema, pair-objects, pairing function, un-pairing (projection) function 假设 X, Y, O 是对象的集合（它们可以是相同的或者是不同的）。 有 $pr: X, Y \to O$ 是一个二元函数 (tow-place function)， 同时有 $\pi_1 : O \to X$ 和 $\pi_2 : O \to Y$ 是 one-place function。 这样 $[O, pr, \pi_1, \pi_2]$ 形成一个对 X、Y 的结对模式，当且仅当满足条件： a:π1(pr(x,y))=x&π2(pr(x,y))=y,∀x∈X,∀y∈Y b:pr(π1(o),π2(o))=o,∀o∈O

  这样，O 被称为这个结对模式的结对对象 (pair-objects)， $pr$ 为关联的结对函数 (pairing function)， $\pi_1$ 和 $\pi_2$ 是反结对函数 (映射函数)(un-pairing or projection functions)。

• 定理：如果 $[O, pr, \pi_1, \pi_2]$ 是一个结对模式，那么：

  1. $pr$ 不同的输入对生成不同的结对对象。
  2. $pr, \pi_1, \pi_2$ 都是满射。

• 定理： 如果 $[O, pr, \pi_1, \pi_2]$ 和 $[O, pr, \pi''_1, \pi''_2]$ 都是 X 和 Y 的结对模式，则 $\pi_1 = \pi''_1, \pi_2 = \pi''_2$。 如果 $[O, pr, \pi_1, \pi_2]$ 和 $[O, pr'', \pi_1, \pi_2]$ 都是 X 和 Y 的结对模式，则 $\pr = \pr''$。

• 定理： 如果 $[O, pr, \pi_1, \pi_2]$ 和 $[O'', pr'', \pi''_1, \pi''_2]$ 都是 X 和 Y 的结对模式，则存在一个唯一的双射 (bijection)$f : O \to O''$，有 $pr''(x, y) = f (pr (x, y)), \forall x \in X, \forall y \in Y$。

• 定理 假设 X, Y, O 是对象集合，和函数 $\pi_1 : O \to X, \pi_2 : O \to Y$，如果有一个唯一的 two-place 函数 $pr: X, Y \to O$，满足条件 (a): a:π1(pr(x,y))=x&π2(pr(x,y))=y,∀x∈X,∀y∈Y

  则，$[O, pr, \pi_1, \pi_2]$ 满足条件 (b)，从而形成一个结对模式。

• 定义：乘积 如果 X, Y 是集合，那么 $[O, \pi_1, \pi_2]$ 形成一个 X 和 Y 的乘积， 这里面: O 是一个集合， $\pi_1 : O \to X$ 是一个函数， $\pi_2 : O \to Y$ 是一个函数， 有一个唯一的 two-place 函数：$pr : X, Y \to O$，有 $\pi_1 (pr (x, y)) = x \And \pi_2 (pr (x, y)) = y, \forall x \in X, \forall y \in Y$。

二元乘积

• 定义：二元乘积 (binary product) 在任何一个范畴中，一个对于 X 和 Y 的二元乘积 $[O, \pi_1, \pi_2]$ 是一个对象 O 和映射箭头 $\pi_1 : O \to X, \pi_2 : O \to Y$ 的组合。 这样对于任何对象 $S$ 和箭头 $f_1 : S \to X, f_2 : S \to Y$，总有一个协调箭头 (mediating arrow)$u : S \to O$ 形成一个交换图。

• 定义：楔子 (wedge) 对于 X 和 Y 的一个楔子是一个对象 S 和一对儿箭头 $f_1 : S \to X, f_2 : S \to Y$。 一个楔子 $[O, \pi_1, \pi_2]$ 是 X 和 Y 的乘积，当且仅当，对于 X 和 Y 的任何其它楔子 $[S, f_1, f_2]$，存在一个唯一的态射 $u : S \to O$ 形成一个交换图。

• 定义：衍生楔子范畴 (derived wedge category) 给定一个范畴 $\mathcal {C}, X, Y \in Ob (\mathcal {C})$，衍生楔子范畴 (derived wedge category)$\mathcal {C}_{W (XY)}$ 是： 对象数据是 X 和 Y 的所有楔子 $[O, f_1, f_2]$； $[O, f_1, f_2]$ 和 $[O'', f''_1, f''_2]$ 的箭头是范畴 $\mathcal {C} 的箭头 $g : O \to O''$； $[O, f_1, f_2]$ 单位箭头是 $1_O$； 箭头组合相同于范畴 $\mathcal {C}$ 的箭头组合。

• 定义：在 $\mathcal {C}$ 中，一个 X 和 Y 的乘积是衍生范畴 $\mathcal {C}_{W (XY)}$ 一个终点对象。

唯一同构

范畴 $\mathcal {C}$ 中，对于任意的对象 X 和 Y，乘积不一定存在；如果存在，也不一定唯一。

• 定义：Uniqueness up to unique isomorphism 如果 $[O, \pi_1, \pi_2]$ 和 $[O'', \pi_1'', \pi_2'']$ 是对象 X 和 Y 的乘积， 那么存在一个唯一的同构 $f: O \sim \over \longrightarrow O''$ 联系与影射箭头 (有：$\pi_1'' \circ f = \pi_1, \pi_2'' \circ f = \pi_2$)。

协乘积 (co-product)

• 定义：范畴化定义楔子的对偶 (the duals) 通常被称为协楔子。这样一个范畴 C 的协楔子是协范畴 $C^{op}$ 的一个楔子。

• 定义：协乘积 (co-product) 范畴 $\mathcal {C}$ 中，对于任意的对象 X 和 Y，一个二元协乘积 $[O, l_1, l_2]$ 是： 一个对象 O， 两个影射箭头：$l1: X \to O, l2: Y \to O$。 这样，对于任何 S 和箭头 $f_1: X \to S, f_2 : Y \to S$，有一个唯一的协调箭头：$v : O \to S$ 形成一个交换图。 协乘积记为： $X \oplus Y$

8 探索乘积

• 定理：在有一个终点对象的范畴中

  1. 存在乘积 $1 \times X$ 和 $X \times 1$，并且有 $1 \times X \simeq X \simeq X \times 1$。
  2. $X \times Y \simeq Y \times X$
  3. $X \times ( Y \times Z ) \simeq ( X \times Y ) \times Z$

• 定理：有这样的范畴，其中总是存在乘积 $0 \times X$ 或者 $X \times 0$，但是这个乘积通常不同构与 0。

• 定理 如果 $1 \overset {!_{1 \times X}}{\longleftarrow} 1 \times X \overset {i}{\longrightarrow} X$ 是一个乘积 则：$i$ 是一个同构。

• 定义：调解箭头 (mediating arrow) 的一种表示 假设 $[O, \pi_1, \pi_2]$ 是一个对象 X 和 Y 的二元乘积，假设有一个楔子 $X \overset {f_1}{\Longleftarrow} S \overset {f_2}{\longrightarrow} Y$， 通过一个调解箭头 $u : S \to O$，形成一个交换图。 这个调解箭头 $u : S \to O$ 科表示为 $<f_1, f_2>$。

• 定理： $<f_1, f_2> = <g_1, g_2> \implies f_1 = g_1, f_2 = g_2$。

• 定理 对于乘积 $[X \times Y, \pi_1, \pi_2]$ 和箭头 $u: S \to X \times Y, v: S \to X \times Y$， 如果有 $\pi_1 \circ u = \pi_1 \circ v, \pi_2 \circ u = \pi_2 \circ v \implies u = v$。

• 定义：对角态射 (diagonal morphism) 对于乘积 $[X \times X, \pi_1, \pi_2]$ 和箭头 $\pi_1: X \times X \to X, \pi_2: X \times X \to X$， 楔子 $X \overset {1_X}{\Longleftarrow} X \overset {1_X}{\longrightarrow} X$， 它们对应的调解箭头 $<1_X, 1_X>$ 为对角态射，记做 $\delta_x$。

• 定理： $q: S \to X \implies \delta_x \circ q = <q, q>$。

• 定理： $<f, g> \circ e = <f \circ e, g \circ e>$

• 定理： 给定平行箭头 $f_1: S \to X, f_2 : S \to X, f_1 \neq f_2$，那么至少有 4 个箭头 $S \to X \times X$。

两个乘积之间的匹配

• 定义：两个乘积之间的匹配: $f \times g$

f:X→X′ g:Y→Y′ [X×Y,π1,pi2] [X′×Y′,π′1,π′2] f×g:X×Y→X′×Y′ π′1∘f×g=f∘π1 π′2∘f×g=g∘π2

• 定理： 假设 $f: X \to X, g: Y \to Y, o: X \times Y \to Y \times X {(x, y) \to (y, x)}$， 得出：$(f \times g) \cirs o = (g \times f) \circ o$。

• 定理： 存在双箭头 $f, g: X \to Y$，和乘积 $X \times X, Y \times Y$， 则：楔子 $<f, g> = （f \times g） \circ \theta_x$。

• 定理 37 有平行箭头 $f: X \to X'', j: X'' \to X", g: Y \to Y'', k: Y'' \to Y"$， 和乘积 $[X \times Y, \pi_1, \pi_2], [X'' \times Y'', \pi''_1, \pi''_2], [X"\times Y", \pi"_1, \pi"_2]$， 则：$(j \times k) \circ (f \times g) = (j \circ f) \times (k \circ g)$。

有限元乘积

• 定义 44：有限元乘积 对于 $X_1, \cdots, X_n$ 的乘积 $O, \pi_1, \cdots, \pi_n$， 对于任意的 S 和箭头 $f_i : S \to X_i$，存在一个唯一的协调箭头 $u: S \to O$，$f_i = \pi_i \circ u$

• 定理 38 在一个范畴里，对于 $X_1, X_2, X_3$, 如果有三元乘积 $[O, \pi_1, \pi_2, \pi_3]$ 和 $O, \pi''_1, \pi''_2, \pi''_3$， 那么存在一个唯一的同构 $u: O \simeq O''$

• 定理 39 $(X_1 \times X_2) \times X_3$ 形成一个 $X_1, X_2, X_3$ 的三元乘积。

• 定义 45： 范畴 $\mathcal {C}$ 有所有的二元乘积，$\iff$ 对于任意的两个对象，这个范畴都有乘积。 范畴 $\mathcal {C}$ 有所有的有限元乘积，$\iff$ 对于任意的 n 个对象，这个范畴都有 n 元乘积，$n \geqslant 0$。

• 定理 40 范畴 $\mathcal {C}$ 有所有的有限元乘积，$\iff$ 这个范畴有一个终点对象，并且有所有的二元乘积。

无限乘积

• 定义 46：无限乘积 (infinite products) 假设范畴 $\mathcal {C}$ 中，对象 $X_j$ 可以在一套索引 $J$ 中通过 j 索引，$J$ 是一个无限的。 如果，对于每个 $X_j$ 的乘积 $O$，有 $\pi_j : O \to X_j$， 同时需要对于任意的对象 $S$ 和箭头族 $f_j ： S \to X_j$，有 $u : S \to O, \And f_j = \pi_j \circ u, \forall j$。

• 定义 47： 范畴 $\mathcal {C}$ 有所有的乘积，$\iff$ 对于任意的对象 $X_j | j \in J$，这个范畴都有乘积，记做 $\prod_{j \in J}{X_j}$。

均衡器 (Equalizers)

• 定义 48: 叉子 (fork) 一个叉子 (从 S 通过 X 到 Y)，包含箭头 $k: S \to X, f: X \to Y, g: X \to Y, f \circ k = g \circ k$，是一个交换图。

• 定义 49 均衡器 (Equalizer) 在一个范畴中，有平行箭头 $f, g : X \to Y$，一个均衡器：$E, e: E \to X$，需要满足以下条件：

  1. $f \circ e = g \cire e$，也就是说 E,X,Y 形成一个叉子。
  2. 任意的其它叉子 $S, X, Y, s: S \to X$，存在一个唯一的协调箭头 (mediating arrow)$u: S \to E$。

均衡器是一个约束 (limiting case)

• 定义 50：叉子范畴 在范畴 $\mathcal {C}$ 中，$f,g：X \to Y$ 形成的叉子 $k: S \to X; g, f: X \to Y$， 可以得到一个衍生叉子范畴 $\mathcal {C_{F (fg)}}$，如下： 对象：每个 $S \to X; g, f: X \to Y$ 为一个对象； 箭头：$u: (S \to \cdots) \to (S'' \to \cdots)$ 是范畴 $\mathcal {C}$ 中的 $u : S \to S''$； 显而易见有交换图：$k = k'' \circ u$； 单位箭头：$1_{(S \to \cdots)} = 1_S$； 结合律：就是范畴 $\mathcal {C}$ 中的结合律。

• 定义 51：叉子范畴的终点对象 在一个范畴中，平行箭头 $f, g : X \to Y$ 的均衡器：$E, e: E \to X$，其对应在衍生叉子范畴的对象是一个终点对象。

唯一性

• 定理 41：均衡器之间存在唯一的同构 在范畴 $\mathcal {C}$ 中，$f,g：X \to Y$ 的均衡器 $[E, e], [E'', e'']$ 存在唯一的同构：$j: E \to E''$， 形成交换图：$e = e'' \circ j$。

• 定理 42： 如果 $[E, e]$ 构成一个均衡器，那么 $e$ 是一个单态射 (monomorphism).

• 定理 43： 一个满态射的均衡器是一个同构态射。

协均衡器 (co-equalizers)

• 定义 52: 协叉子 (co-fork) 一个协叉子 (从 X 通过 Y 到 S)，包含箭头 $f, g: X \to Y; k: S \to X,; \And k \circ f = k \circ g$。

• 定义 53 协均衡器 (Co-Equalizer) 在一个范畴中，有平行箭头 $f, g : X \to Y$，一个协均衡器：$C, c: Y \to C$，需要满足以下条件：

  1. $c \circ f = c \cire g$，也就是说 C,X,Y 形成一个协叉子。
  2. 任意的其它协叉子 $S, X, Y, s: Y \to S$，存在一个唯一的协调箭头 (mediating arrow)$u: C \to S$。

• 定义 R 对于平行箭头 $f,g: X \to Y$，可以引出一个对于对象 Y 的元素之间的关系 R (或者记做 $R_{fg}$)。 $yRy''$ 意味着 $f (x) = y \And g (x）= y'', \exists x \in X$。 在一个协叉子中，意味着 $yR_{fg} y''\implies k (y) = k (y'')$，有记做 $y \equiv_k y''$。

• 定义 R 的最小等价关系 (the smallest equivalence relation R) $R~$ $R^~$ 需要包括一个箭头 $c: Y \to C, c (y) = c (y'') \iff yRy''$，或者说 $\equiv_c = R~$。

• 定理 44 $C = Y/R~; c: Y \to C$，c 映射 y 到包含 y 的 C 元素上。$[C, c]$ 构成一个 $f, g$ 的协均衡器。 举例： $Y = [a, a'', b, b'', d, d''], aRa'', bRb'', dRd''$ $C = Y/R~ = [[a, a''], [b, b''], [d, d'']]$ $c (a) = [a, a'']$

10 限制和协限制 (limits and co-limits defined)

锥 (cone)

• 定义 图表 (diagram) 一个基于范畴中的 diagram，是一些（或者没有）对象 $D_j$，这些对象可以按照索引 $J$ 通过序号 $j$ 来定位，和一些 (或者没有)$D_j$ 之间的箭头。

• 定义 54 图表的锥 (cone) 对于一个图表 D 的锥 (cone over a diagram)，其构成为 $[C, c_j: C \to D_j] | j \in J]$， 并且对于图表中的任意箭头 $d: D_i \to D_j$，有交换关系 $c_j = d \circ c_i$。

• 定义 55 图表的闭包 (closure) 对于一个 ** 图表 D 的闭包 (closure)** 是一个最小的图表，并包含：

  1. D 的所有对象和箭头
  2. D 所有对象的单位箭头
  3. 如果有两个箭头的可组合的 (compos-able)，那么要包含它们的组合箭头。

• 定理 45 一个闭包是一个子范畴。

• 定理 46 如果，$[C, c_j]$ 是图表 D 的锥，则也是图表 D 的闭包的锥。

极限锥 (limit cone)

• 定义 56 图表的极限锥 (limit cone) 图表 D 的极限锥 (limit cone)$[L, \lambda_j]$ 的满足条件： 对于图表 D 的任意一个锥 C，都存在一个唯一的协调箭头 $k: C \to L, \lambda_j \circ k = c_j | \forall j \in J$。

• 定理 47 一个给定图表的所有极限锥之间，一对一之间都存在唯一的同构，这个同构与锥箭头之间形成了交换。

• 定义 56 派生范畴：图表的锥范畴 一个范畴 $\mathcal {C}$ 中，对于图表 D，可以派生含有图表 D 上所有锥的范畴，记做 $\mathcal {C}_{C (D)}$:

  1. 对象：所有锥 $[C, c]$
  2. 箭头：任意 C 之间的箭头 $k: C \to C''$，并满足 $c''_j \circ k = c_j, j \in J$
  3. 单位对象：$1_C$
  4. 组合关系：箭头的原组合关系。

• 定理 58 一个范畴 $\mathcal {C}$ 中，图表 D 的极限锥是图表的锥范畴 $\mathcal {C}_{C (D)}$ 的终点对象。

• 定理 48 一个范畴 $\mathcal {C}$ 中，$[L, \lambda]$ 是图表 D 的极限锥， $[L'', \lambda'']$ 是图表 D 的锥，并且通过 $f: L'' \to L$ 构成一个同构， 则：$[L'', \lambda'']$ 是图表 D 的极限锥。

• 定理 49 TBD

• 定理 50 一个范畴 $\mathcal {C}$ 有一个起点对象，当且仅当范畴 $\mathcal {C}$ 作为一个图表有一个极限锥。

• 定义 59 极限对象 对于一个图表 D 的一个极限锥，我们将位于这个极限锥的顶点的极限对象，自作 $\lim_{\rightarrow j} D_j$。

协极限 (colimits)

• 定义 60: 协锥 (co-cone) 一个图表 D 的协锥 C，有：
  1. $c_j: D_j \to C, j \in J$
  2. $c_k = c_l \circ d, \forall d: D_k \to D_l$

撤回 (Pullbacks)

• 定义 61：撤回，撤回正方形 (pullback square) 对于一个角图 (corner diagram) 的一个极限 (limit)$[L, \lambda_1: L \to D_1, \lambda_2: L \to D_2]$ 是一个撤回。 一个角图和极限组成一个撤回正方形 (pullback square)。 corner diagram: $D_1, D_2, D_3, d: D_1 \to D_3, e: D_2 \to D_3$。

• 定理 51 撤回一个单态射，产生一个单态射。

• 定理 52 $f: X \to Y$ 是一个单态射，当且仅当下面是一个撤回正方形： $1_X: X \to X, f: X \to Y$ $1_X: X \to X, f: X \to Y$

• 定理 53 一个顶点为 Z 的角的撤回是商范畴 $\mathcal {C}/Z$ 的一个乘积。

推出 (pushout)

• 定义 62：一个楔子图的极限是一个推出 (pushout)。

11 极限的存在性

• 定义 63：一个包含所有有限极限的范畴，被称为有限地完整。 有限极限：对于有限图 D（任意图包含 D，并拥有有限的索引 J）。

12 子对象 (sub-object)

13 指数 (Exponential)

14 组对象，自然数对象

15 函子 (Functor)

16 范畴的范畴 (Categories of categories)

17 函子和极限 (functors and limits)

18 同态函子 (Hom-functors)

19 函子和逗号范畴

20 自然的同构 (Natural isomorphisms)

21 自然的变形 (Natural transformations)

22 函子范畴 (Functor categories)

23 范畴的等价性 (Equivalent categories)

24 Yoneda 植入 (The Yoneda embedding)

25 Yoneda 推论 (The Yoneda Lemma)

26 可表达和统一元素 (Representables and universal elements)

27 Galois 连接 (Galois connections)

28 伴随的介绍 (Adjoints introduced)

• 定义 125 伴随 (adjoint) 范畴 $\mathcal {A}, \mathcal {B}$，和函子 $F: \mathcal {B} \to B, G: \mathcal {B} \to \mathcal {A}$。 则 $F$ 是 $G$ 的左伴随，则 $G$ 是 $F$ 的右伴随，记做：$F \dashv G$。 前提条件: $\mathcal {B}(F (A), B) \simeq \mathcal {A}(A, G (B))$。

29 伴随的更多探索 (Adjoints further explored)

30 伴随函子和极限 (Adjoints functors and limits)

附

符号

Isomorphism: $\simeq$ iff: $\iff$

各种理解

• 结合律的理解 结合律意味着可以在任何一个计算点开始计算。

• 如何证明单射 (injective) 通过假设两个元素 e, e'' 的射结果相同，既 $f (e) = f (e'')$，如果可以推导出 $e = e''$，则 $f$ 是一个单射。

• 如何证明满射 (surjective) 对于任何 $b \in B$，$f (a) = b, \exists a \in A$。

• 如何证明同构 $\simeq$(isomorphism) 对于任何 $b \in B$，存在 $f (a) = b, a \in A$。

• 交换图 各种表达：commuting with arrows, form a diagram commuting, triangle commutes, etc. 其中的含义是：从对象 A 到对象 B 存在两个相等的路径。

• 协调箭头 (mediate arrows) 一种常见的交换图形式。总是以这样的形式出现： 有一组源对象和一个目标对象，存在：$[S_j, s_j: S \to T], j \in J$， 有一个对象 $[M, m: M \to T]$，对于每个源对象，存在唯一的： $k: S_j \to M; \And m \circ k = s_j$。 $k$ 就是协调箭头。 这里，似乎说明了 $[M, m]$ 有一种特性，存在一个等价的交换路径。

冯诺依曼 (Von Neumann) 的自然数定义

0=∅ 1=∅ 2=∅,∅ 3=∅,∅,∅,∅ ⋯ n+1=n∪n

参照

• Category Theory A Gentle Introduction by Peter Smith (University of Cambridge)
• Wikipedia

com.intellij.ui.treeStructure.actions.ExpandAllAction的实例源码

public ActionToolbar createGroupFilterToolbar(final Project project,final ActionGroup leadGroup,@Nullable final ActionGroup tailGroup,final List<AnAction> extra) {
  DefaultActionGroup toolbarGroup = new DefaultActionGroup();
  toolbarGroup.add(leadGroup);
  toolbarGroup.addSeparator();
  toolbarGroup.add(new SelectFilteringAction(project,this));
  toolbarGroup.add(new SelectGroupingAction(project,this));
  final ExpandAllAction expandAllAction = new ExpandAllAction(myChangesTree);
  final CollapseAllAction collapseAllAction = new CollapseAllAction(myChangesTree);
  expandAllAction.registerCustomShortcutSet(
    new CustomShortcutSet(KeymapManager.getInstance().getActiveKeymap().getShortcuts(IdeActions.ACTION_EXPAND_ALL)),myChangesTree);
  collapseAllAction.registerCustomShortcutSet(
    new CustomShortcutSet(KeymapManager.getInstance().getActiveKeymap().getShortcuts(IdeActions.ACTION_COLLAPSE_ALL)),myChangesTree);
  toolbarGroup.add(expandAllAction);
  toolbarGroup.add(collapseAllAction);
  toolbarGroup.add(ActionManager.getInstance().getAction(VcsActions.ACTION_copY_REVISION_NUMBER));
  toolbarGroup.add(new ContextHelpAction(myHelpId));
  if (tailGroup != null) {
    toolbarGroup.add(tailGroup);
  }
  for (AnAction anAction : extra) {
    toolbarGroup.add(anAction);
  }
  return ActionManager.getInstance().createActionToolbar(ActionPlaces.UNKNowN,toolbarGroup,true);
}

protected ActionGroup createActionGroup() {
  DefaultActionGroup result = new DefaultActionGroup();
  Sorter[] sorters = myTreeModel.getSorters();
  for (final Sorter sorter : sorters) {
    if (sorter.isVisible()) {
      result.add(new TreeActionWrapper(sorter,this));
    }
  }
  if (sorters.length > 0) {
    result.addSeparator();
  }

  addGroupByActions(result);

  Filter[] filters = myTreeModel.getFilters();
  for (Filter filter : filters) {
    result.add(new TreeActionWrapper(filter,this));
  }
  if (myTreeModel instanceof ProvidingTreeModel) {
    final Collection<NodeProvider> providers = ((ProvidingTreeModel)myTreeModel).getNodeProviders();
    for (NodeProvider provider : providers) {
      result.add(new TreeActionWrapper(provider,this));
    }
  }

  result.add(new ExpandAllAction(getTree()));
  result.add(new CollapseAllAction(getTree()));

  if (showScrollToFromSourceActions()) {
    result.addSeparator();

    result.add(myAutoScrollToSourceHandler.createtoggleAction());
    result.add(myAutoScrollFromSourceHandler.createtoggleAction());
  }
  return result;
}

protected ActionGroup getPopupActions() {
  DefaultActionGroup group = new DefaultActionGroup();

  group.add(ActionManager.getInstance().getAction("DomElementsTreeView.TreePopup"));
  group.addSeparator();

  group.add(new ExpandAllAction(myTree));
  group.add(new CollapseAllAction(myTree));

  return group;
}

private ActionGroup getPopupActions() {
  DefaultActionGroup group = new DefaultActionGroup();

  group.add(new ExpandAllAction(myTree));
  group.add(new CollapseAllAction(myTree));
  group.addSeparator();
  group.add(new RevealFileAction());
  group.add(new DeleteAction());
  group.addSeparator();
  group.add(new RunHprofConvAndSaveAsAction());

  return group;
}

public ActionToolbar createGroupFilterToolbar(final Project project,this));
  toolbarGroup.add(new SelectGroupingAction(this));
  final ExpandAllAction expandAllAction = new ExpandAllAction(myChangesTree);
  final CollapseAllAction collapseAllAction = new CollapseAllAction(myChangesTree);
  expandAllAction.registerCustomShortcutSet(
    new CustomShortcutSet(KeymapManager.getInstance().getActiveKeymap().getShortcuts(IdeActions.ACTION_EXPAND_ALL)),myChangesTree);
  toolbarGroup.add(expandAllAction);
  toolbarGroup.add(collapseAllAction);
  toolbarGroup.add(ActionManager.getInstance().getAction(IdeActions.ACTION_copY));
  toolbarGroup.add(new ContextHelpAction(myHelpId));
  if (tailGroup != null) {
    toolbarGroup.add(tailGroup);
  }
  for (AnAction anAction : extra) {
    toolbarGroup.add(anAction);
  }
  return ActionManager.getInstance().createActionToolbar(ActionPlaces.UNKNowN,true);
}

protected DefaultActionGroup createActionGroup(boolean togglesOnly) {
  DefaultActionGroup result = new DefaultActionGroup();
  Sorter[] sorters = myTreeModel.getSorters();
  for (final Sorter sorter : sorters) {
    if (sorter.isVisible()) {
      result.add(new TreeActionWrapper(sorter,this));
    }
  }

  if (!togglesOnly) {
    result.add(new ExpandAllAction(getTree()));
    result.add(new CollapseAllAction(getTree()));
  }

  if (showScrollToFromSourceActions()) {
    result.addSeparator();

    result.add(myAutoScrollToSourceHandler.createtoggleAction());
    result.add(myAutoScrollFromSourceHandler.createtoggleAction());
  }
  return result;
}

protected ActionGroup getPopupActions() {
  DefaultActionGroup group = new DefaultActionGroup();

  group.add(ActionManager.getInstance().getAction("DomElementsTreeView.TreePopup"));
  group.addSeparator();

  group.add(new ExpandAllAction(myTree));
  group.add(new CollapseAllAction(myTree));

  return group;
}

public ActionToolbar createGroupFilterToolbar(final Project project,this));
  final ExpandAllAction expandAllAction = new ExpandAllAction(myChangesTree);
  final CollapseAllAction collapseAllAction = new CollapseAllAction(myChangesTree);
  expandAllAction.registerCustomShortcutSet(new CustomShortcutSet(KeymapManager.getInstance().getActiveKeymap().getShortcuts(IdeActions.ACTION_EXPAND_ALL)),myChangesTree);
  collapseAllAction
          .registerCustomShortcutSet(new CustomShortcutSet(KeymapManager.getInstance().getActiveKeymap().getShortcuts(IdeActions.ACTION_COLLAPSE_ALL)),true);
}

protected DefaultActionGroup createActionGroup() {
  DefaultActionGroup result = new DefaultActionGroup();
  if (addCustomActions(result)) {
    result.addSeparator();
  }

  Sorter[] sorters = myTreeModel.getSorters();
  for (final Sorter sorter : sorters) {
    if (sorter.isVisible()) {
      result.add(new TreeActionWrapper(sorter,this));
    }
  }

  result.add(new ExpandAllAction(getTree()));
  result.add(new CollapseAllAction(getTree()));

  if (showScrollToFromSourceActions()) {
    result.addSeparator();

    result.add(myAutoScrollToSourceHandler.createtoggleAction());
    result.add(myAutoScrollFromSourceHandler.createtoggleAction());
  }
  return result;
}

protected ActionGroup getPopupActions() {
  DefaultActionGroup group = new DefaultActionGroup();

  group.add(ActionManager.getInstance().getAction("DomElementsTreeView.TreePopup"));
  group.addSeparator();

  group.add(new ExpandAllAction(myTree));
  group.add(new CollapseAllAction(myTree));

  return group;
}

com.intellij.ui.treeStructure.AlwaysExpandedTree的实例源码

private boolean isAlwaysExpandedTree() {
  return myTree instanceof AlwaysExpandedTree && ((AlwaysExpandedTree)myTree).isAlwaysExpanded();
}

private boolean isAlwaysExpandedTree() {
  return myTree instanceof AlwaysExpandedTree && ((AlwaysExpandedTree)myTree).isAlwaysExpanded();
}

private boolean isAlwaysExpandedTree() {
  return myTree instanceof AlwaysExpandedTree && ((AlwaysExpandedTree)myTree).isAlwaysExpanded();
}

我们今天的关于Tree Structure 和Recursion的分享就到这里，谢谢您的阅读，如果想了解更多关于A Fast Wait-Free Simulation for Lock-Free Data Structures、Category Theory: 01 One Structured Family of Structures、com.intellij.ui.treeStructure.actions.ExpandAllAction的实例源码、com.intellij.ui.treeStructure.AlwaysExpandedTree的实例源码的相关信息，可以在本站进行搜索。