老規(guī)矩cc0。

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

關(guān)于ADT，抽象數(shù)據(jù)類型這種東西，相信所有對算法和數(shù)據(jù)結(jié)構(gòu)有所了解的朋友都應(yīng)該至少有所耳聞。

但是，什么是抽象數(shù)據(jù)類型呢？

數(shù)學(xué)上，抽象數(shù)據(jù)類型總是代表著某種代數(shù)結(jié)構(gòu)，但是，

某種ADT是某種類型，再加上在這個類型上定義的一組操作。

類型關(guān)心的是值的集合本身，而ADT關(guān)心的則是這組操作：ADT實際上并不關(guān)心值，只要值(一類值)具有ADT關(guān)心的這組操作，那么這類值就自動得被這個ADT所描述。

所以說ADT是代數(shù)結(jié)構(gòu)嘛

比如說我們定義有兩種元素的集合{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關(guān)心的是二元操作+和*，卻并不關(guān)心A和B具體是什么。

另外，這是一個半環(huán)

實際上ADT也反過來聲明了一種類型：所有被這個ADT描述的類型的值的集合，就是這個ADT所聲明的類型。這種類型的聲明方式在現(xiàn)代編程語言種有著非常重要的地位：interface，template, generic和duck typing都可以看作(某種)通過ADT聲明類型的方式。

不過generic和template太過具體并且包含實現(xiàn)，而interface和duck typing對操作的限制又過少。

為什么抽象數(shù)據(jù)類型是有用的

從某種意義上說，抽象數(shù)據(jù)類型不過是另一種定義值集合和類型的方式，但抽象數(shù)據(jù)類型的確與眾不同：因為抽象數(shù)據(jù)類型關(guān)心操作。

例如你現(xiàn)在有許多工作需要做，這些工作對你來說的重要程度各不相同，那么一個好的方法就是將這些工作排序。而這時，具體類型“工作”就表現(xiàn)出了其抽象類型“Comparable”的側(cè)面，在排序時，你不需要關(guān)心具體類型，你需要關(guān)心的是Comparable。Comparable關(guān)心的是比較操作，而編程關(guān)心的也正是操作。

而當(dāng)你在做工作時，你關(guān)心的是這一工作的“Doable”，而不關(guān)心Comparable：實際上代碼中需要將某個具體類型作為整體把握的場合很少，相反，每一部分代碼都是在關(guān)心其具有的某個抽象類型。而實際上，這一整個流程都可以抽象為，

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

相較于具體類型，抽象數(shù)據(jù)類型將真正需要關(guān)心的東西抽象了出來，而忽略了不需要關(guān)心的其他部分和具體實現(xiàn)。

最后：關(guān)于操作

很多人和語言把操作狹義得理解為operator或是function，但是property實際上也是一類操作(或者說兩類)，而又因為字段(或者說，自動屬性)與屬性是不可區(qū)分的，因此字段實際上也是操作——

但這并不是說任何涉及具體實現(xiàn)的字段都應(yīng)被視為操作：歸類于操作的字段應(yīng)當(dāng)是有意義的。

例如說，Complex的實部，虛部，幅，輻角這些字段，其getter和setter都具有對應(yīng)的操作語義，其中可能存在某兩個量屬于自動屬性，但哪些量屬于自動屬性并不重要：因為它們只與實現(xiàn)相關(guān)。

當(dāng)然，在不支持屬性的語言中，字段就沒有這種地位了：在這種語言中，接口/抽象基類定義永遠不應(yīng)該包含字段。

討論1：操作是類型的性質(zhì)還是值的性質(zhì)？

四則運算是定義在number集合上的，因而看起來似乎是類型的性質(zhì)。但我們也可以這樣看：四則運算是number中每一個值的性質(zhì)。這種視角似乎沒有意義，但在某些場合是有意義的。

我們有兩只鳥，但其中一只翅膀受傷了不會飛。那么這只受傷的鳥便不具有“起飛”這一操作。當(dāng)然，你可以說操作“起飛”是類型“會飛的鳥”的性質(zhì)，但實際上會飛的不只有鳥，還有飛機和馬老師，這等于是說，這是“會飛的”這一ADT的性質(zhì)——

但是鳥的會飛是先于這一ADT的。

也就是說，操作首先是值的性質(zhì)，進而是ADT的性質(zhì)，具體類型并不必然有任何操作性質(zhì)：因此操作不應(yīng)該是定義在具體類型之上的：它要么應(yīng)該被定義在ADT上，要么應(yīng)該被定義在值上。

這也就是class-based OO的問題所在：這種OO不允許直接在值上定義操作，如果想要這樣做，就需要為某個值建立“只含有這個值本身”的類型，也就是所謂“單例”。

而另一方面，class-based OO卻少有允許在ADT上定義(實現(xiàn))操作，C++算是一個特例，另一個(并不完全屬于class-based)的特例是rust的default implementation。不過越來越多的class-based語言開始允許interface提供默認實現(xiàn)，這是很有趣的事情。

不過另一方面，prototype-based OO，因為更難實現(xiàn)多繼承，所以雖然允許值提供實現(xiàn)，卻并沒有允許ADT提供實現(xiàn)，算是一點瑕疵：當(dāng)然，JavaScript是沒有interface的，其ADT是通過duck typing定義的所以也就，只能這樣了。

但是typescript還是提供一下interface的default implementation比較好：不過似乎ts只想做類型擦除，這就又很令人無奈了。

但是吧，畢竟ts連強類型語言都不是，也就，理解一下好了。

討論2：Object的可變性是JavaScript的又一大錯誤嗎？

說實話，Object的可變性是一種妥協(xié)：真正實現(xiàn)了Object不可變的那些語言，也就是那些純函數(shù)式語言，為了這一不可變性付出了很多代價。

當(dāng)然這實際上也會在編程思路上帶來巨大差別：值本身不可變但狀態(tài)必須被記錄，所以每一次的狀態(tài)變化都要求以新值替代舊值，這種對替代的要求當(dāng)然也有很多好處，但是對設(shè)計思路的考驗是更大的。

不過immutableJS的確是很有趣的。