『盒子(不能直接取出内部物品的)』的比喻对范畴论来说虽然很不正确（因为盒子只是有封闭律和结合律、identity的图），但你会发现没有这个『盒子』的理解和举例，你根本不会理解 Functor, Applicative, Monad, State, 甚至只是 Identity/Maybe 那一套；即便别人解释得再简单、再可视化也不行，所以说知识到底还是要『讲』出重点的。

好比我开始想Dijkstra算法基本思路的时候，肯定要问『为什么每次要选余下节点里最小的更新权重，如果选中位数、极大(Max)值，甚至干脆随便选会怎么样？』这个问题，要不然你肯定无法理解算法需要输入数据满足的性质和它做的断言、不会知道为什么不能有『负权边』。
— 因为它做了一个断言：『任何可能是某点前驱的节点，其距离绝对小于该点』，这是为了在不连续的搜索过程中保证从『当前搜索路径』一直能够得到等价的新源点、保证一个点的距离被传递前它的所有可能路径均已经求得最短，所以不能有负权边。

可见对知识的第一印象是很重要的，错的第一印象看起来会导致谬误，但是没有能让人理解的第一印象就没有进步。
所以比起老是对『知识不准确』患得患失，不如踏踏实实先学一个不恰当的比喻，然后在以后的实践和学习中慢慢加深自己的理解，才可以做到大团圆的结局。

1+1=2？ - 孔良的文章 - 知乎
https://zhuanlan.zhihu.com/p/91153185 #FP
这篇文章是讲范畴论的

前置知识：De Bruijn Index - Trebor的文章 - 知乎
https://zhuanlan.zhihu.com/p/94601499 #PLT #FP

#Java 不能实现真正泛型的原因是什么？ - RednaxelaFX的回答 - 知乎
https://www.zhihu.com/question/28665443/answer/118148143

#dalao 叉姐是谁？ - 程序猴子的回答 - 知乎
https://www.zhihu.com/question/27295079/answer/36054398

阅读早年 Dir 代码的我：wdnmd 这方法干什么的啊..（论不加注释的危害。

说你呢，Telegram Android。

// 但是我没用 stl 的 map<k,v>
template<typename T>
class UnionFind {
private:
T* up; unsigned* size;
T* findFamily(T self)
{ while (up[self] != self) self = up[self]; return self; }
public:
UnionFind(size_t n): up(new T[n]), size(new unsigned[n]) {
for (int i=0; i<n; i++) { up[i]=i; size[i]=0; }
}
boolean connects(T a, T b) { return findFamily(a) == findFamily(b); }
void unite(T a, T b) {
auto pa = findFamily(a), pb = findFamily(b);
if (pa == pb) return;
if (size[pa] < size[pb]) up[pa] = pb, size[pb] += size[pa];
else up[pb] = pa, size[pa] += size[pb];
}
}

带权重的合并树查找（相等关系传递）

#include <bits/stdc++.h>

template<typename T>
class UnionFind { 
private:
  T* up; unsigned* size;
  size_t family(T self)
    { while (up[self] != self) self = up[self]; return self; }
public: 
  UnionFind(size_t n): up(new T[n]), size(new unsigned[n]) {
    for (int i=0; i<n; i++) { up[i]=i; size[i]=1; }
  }
  bool connects(T a, T b) { return family(a) == family(b); }
  void connect(T a, T b) {
    auto pa = family(a), pb = family(b);
    if (pa == pb) return;
    if (size[pa] < size[pb])
         up[pa] = pb, size[pb] += size[pa];
    else up[pb] = pa, size[pa] += size[pb];
  }
}; 

using namespace std;  
const size_t N = 1000;
int main() { int a, b;
  UnionFind<int> uf(N);
  while (cin >> a >> b) {
    if (uf.connects(a, b)) continue;
    uf.connect(a, b); cout <<a<<" "<<b<<endl;
  } 
}  

修复版本

#include <map>
#include <cstddef>

template<typename T>
class UnionFind {  
private:
  template<typename A>
  using M = std::map<T, A>;
  M<T> up; M<unsigned> size;
  T *family(T self) {
    while (up[self] != self) self = up[self];
    return &up[self]; 
  }    
  ~UnionFind() { delete up, size; }
public: 
  explicit UnionFind(size_t n): up(), size() {
    for (int i=0; i<n; i++) up[i]=i, size[i]=1;
  }
  bool connects(T a, T b) { return family(a) == family(b); }
  void connect(T a, T b) { 
    auto fa = family(a), fb = family(b);
    if (fa == fb) return;   
    auto pa = *fa, pb = *fb;
    if (size[pa] < size[pb])
         up[pa] = pb, size[pb] += size[pa];
    else up[pb] = pa, size[pa] += size[pb];
  }
}; 

#include <iostream> 
using namespace std;  
const size_t N = 1000;
int main() { int a, b;
  auto uf = new UnionFind<int>(N);
  while (cin >> a >> b) {
    if (uf->connects(a, b)) continue;
    uf->connect(a, b); cout <<a<<" "<<b<<endl;
  } 
}  

当然也可以用 std::map，不过要实现的话必须定义一个 map 子类型……

总是觉得合并查找不如快速查找优雅，快速 a(up[b]) b(up[c]) c(up[d]) 传递一下就解决了、合并总感觉好像数据结构有点多一样，不好想……

我在想，其实 up 不用 M<T> (non-null)的话，也可以直接上 nullptr, 不就可以在不用子类型判断 contains 的情况下知道一个子树是否为 root 了？

要应用这个修改非常简单：
T *family(T self) {
while (up[self] != nullptr) self = up[self];
return &up[self];
}
explicit UnionFind(size_t n): up(), size() {}
//...
if (size.get_or_init(pa, 1) < size.get_or_init(pb, 1))
up[pa] = pb, size[pb] += size[pa];
else up[pb] = pa, size[pa] += size[pb];
辣鸡C++好像不能用function extendsion?

Haskell 版本的用 Data.Vector 写，可以用 Unboxed 优化（Int 等基本类型）
当然 OI 的话必须 Unboxed.Mutable，传来传去（到处复制） TLE 的
GHC 也得开O2（星野说是「吸氧」）

接下来的计划是：
+ 利用现在的 ParserKt 写出 JSON 和 Kotlin 解析器
+ 讲一下 Infix 解析优化、OverlapRangeMap
+ 编写基本的 Montage Python 程序，生成一些彩色艺术画
+ 写 Binarie 框架
+ 彻底重写 ParserKt

ParserKt 对曾经设计上一个不方便的地方为了想当然的「优雅」少定义了一个接口，结果害得成这样…… Fold 数据结构都有误

我错了！我的定义完全写错了……
可怜的 IDEA，它还帮我指出了 position 分明是一个被该对象 this 引用的 upvalue

它的生命周期已经完全超出应该的每parse一个，导致了这次我浪费大量时间来分析，为什么会出现基于『调用顺序』发生的bug！

这个 Fold 根本不该被定义为 Effect Fold，它应该是普通 Fold 的……