老规矩cc0。

https://creativecommons.org/choose/zero/?lang=zh

关于ADT，抽象数据类型这种东西，相信所有对算法和数据结构有所了解的朋友都应该至少有所耳闻。

但是，什么是抽象数据类型呢？

数学上，抽象数据类型总是代表着某种代数结构，但是，

某种ADT是某种类型，再加上在这个类型上定义的一组操作。

类型关心的是值的集合本身，而ADT关心的则是这组操作：ADT实际上并不关心值，只要值(一类值)具有ADT关心的这组操作，那么这类值就自动得被这个ADT所描述。

所以说ADT是代数结构嘛

比如说我们定义有两种元素的集合{A, B}，这个集合之上有：

* 二元操作+：A+A=A, A+B=B, B+A=B, B+B=B，

* 二元操作*：A*A=A, A*B=A, B*A=A, B*B=B

这样，我们就定义了某种ADT。

我们可以从中看出，这个ADT关心的是二元操作+和*，却并不关心A和B具体是什么。

另外，这是一个半环

实际上ADT也反过来声明了一种类型：所有被这个ADT描述的类型的值的集合，就是这个ADT所声明的类型。这种类型的声明方式在现代编程语言种有着非常重要的地位：interface，template, generic和duck typing都可以看作(某种)通过ADT声明类型的方式。

不过generic和template太过具体并且包含实现，而interface和duck typing对操作的限制又过少。

为什么抽象数据类型是有用的

从某种意义上说，抽象数据类型不过是另一种定义值集合和类型的方式，但抽象数据类型的确与众不同：因为抽象数据类型关心操作。

例如你现在有许多工作需要做，这些工作对你来说的重要程度各不相同，那么一个好的方法就是将这些工作排序。而这时，具体类型“工作”就表现出了其抽象类型“Comparable”的侧面，在排序时，你不需要关心具体类型，你需要关心的是Comparable。Comparable关心的是比较操作，而编程关心的也正是操作。

而当你在做工作时，你关心的是这一工作的“Doable”，而不关心Comparable：实际上代码中需要将某个具体类型作为整体把握的场合很少，相反，每一部分代码都是在关心其具有的某个抽象类型。而实际上，这一整个流程都可以抽象为，

type Job: Comparable & Doable

function doYourJob: (jobs: Set<Job>) → Set<Result>

function sort<T: Comparable>: (items: Set<T>) → Sorted<T>

function do: (job: Doable) → Result

相较于具体类型，抽象数据类型将真正需要关心的东西抽象了出来，而忽略了不需要关心的其他部分和具体实现。

最后：关于操作

很多人和语言把操作狭义得理解为operator或是function，但是property实际上也是一类操作(或者说两类)，而又因为字段(或者说，自动属性)与属性是不可区分的，因此字段实际上也是操作——

但这并不是说任何涉及具体实现的字段都应被视为操作：归类于操作的字段应当是有意义的。

例如说，Complex的实部，虚部，幅，辐角这些字段，其getter和setter都具有对应的操作语义，其中可能存在某两个量属于自动属性，但哪些量属于自动属性并不重要：因为它们只与实现相关。

当然，在不支持属性的语言中，字段就没有这种地位了：在这种语言中，接口/抽象基类定义永远不应该包含字段。

讨论1：操作是类型的性质还是值的性质？

四则运算是定义在number集合上的，因而看起来似乎是类型的性质。但我们也可以这样看：四则运算是number中每一个值的性质。这种视角似乎没有意义，但在某些场合是有意义的。

我们有两只鸟，但其中一只翅膀受伤了不会飞。那么这只受伤的鸟便不具有“起飞”这一操作。当然，你可以说操作“起飞”是类型“会飞的鸟”的性质，但实际上会飞的不只有鸟，还有飞机和马老师，这等于是说，这是“会飞的”这一ADT的性质——

但是鸟的会飞是先于这一ADT的。

也就是说，操作首先是值的性质，进而是ADT的性质，具体类型并不必然有任何操作性质：因此操作不应该是定义在具体类型之上的：它要么应该被定义在ADT上，要么应该被定义在值上。

这也就是class-based OO的问题所在：这种OO不允许直接在值上定义操作，如果想要这样做，就需要为某个值建立“只含有这个值本身”的类型，也就是所谓“单例”。

而另一方面，class-based OO却少有允许在ADT上定义(实现)操作，C++算是一个特例，另一个(并不完全属于class-based)的特例是rust的default implementation。不过越来越多的class-based语言开始允许interface提供默认实现，这是很有趣的事情。

不过另一方面，prototype-based OO，因为更难实现多继承，所以虽然允许值提供实现，却并没有允许ADT提供实现，算是一点瑕疵：当然，JavaScript是没有interface的，其ADT是通过duck typing定义的所以也就，只能这样了。

但是typescript还是提供一下interface的default implementation比较好：不过似乎ts只想做类型擦除，这就又很令人无奈了。

但是吧，毕竟ts连强类型语言都不是，也就，理解一下好了。

讨论2：Object的可变性是JavaScript的又一大错误吗？

说实话，Object的可变性是一种妥协：真正实现了Object不可变的那些语言，也就是那些纯函数式语言，为了这一不可变性付出了很多代价。

当然这实际上也会在编程思路上带来巨大差别：值本身不可变但状态必须被记录，所以每一次的状态变化都要求以新值替代旧值，这种对替代的要求当然也有很多好处，但是对设计思路的考验是更大的。

不过immutableJS的确是很有趣的。