自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

類型的本質(zhì)和函數(shù)式實(shí)現(xiàn)

作者：@文藝復(fù)興記
開(kāi)發(fā) 前端
那么下面我們就先來(lái)認(rèn)識(shí)一下類型到底是什么？我們先以來(lái)看看 表示元素對(duì)的Pair類型，可能有人一提到Pair類型馬上就會(huì)在腦海中浮現(xiàn)出下面的結(jié)構(gòu)：

在上一篇文章《二叉樹(shù)迭代器算法》中，我介紹了一種基于棧的二叉樹(shù)迭代器實(shí)現(xiàn)。程序設(shè)計(jì)語(yǔ)言和Haskell大牛@九瓜 在看過(guò)之后評(píng)論到：

這里用了 stack 來(lái)做，有點(diǎn)偷懶，所以錯(cuò)失了一個(gè)抽象思考機(jī)會(huì)。如果我們能夠理解二叉樹(shù)到線性表的轉(zhuǎn)換過(guò)程，完全可以把 Iterator 當(dāng)作抽象的線性表來(lái)看，只要定義了關(guān)于 Iterator 的 empty, singleton, 還有 append 操作，實(shí)現(xiàn)二叉樹(shù)的 Iterator 就變得非常直觀。

“錯(cuò)失了一個(gè)抽象思考機(jī)會(huì)”是什么意思呢？我理解九瓜的意思是基于棧的實(shí)現(xiàn)雖然是正確的，但它缺乏對(duì)于迭代器類型本質(zhì)的理解，不具有通用性。如果能 對(duì)迭代器進(jìn)行合適地抽象就可以像二叉樹(shù)遞歸遍歷一樣自然地得出二叉樹(shù)迭代器，甚至其他更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，只要我們能寫(xiě)出它的遍歷算法，迭代器算法都可以自 然推出。

類型的本質(zhì)

九瓜提到了通過(guò)empty, singleton和append操作對(duì)Iterator進(jìn)行抽象，我本來(lái)打算直接根據(jù)這個(gè)思路介紹函數(shù)式的二叉樹(shù)迭代器實(shí)現(xiàn)，但是考慮到其實(shí)首要的問(wèn)題 在于理解類型的本質(zhì)，而并不是所有人都具備這個(gè)基礎(chǔ)，不如先普及一下類型基礎(chǔ)再進(jìn)入具體實(shí)現(xiàn)。那么下面我們就先來(lái)認(rèn)識(shí)一下類型到底是什么？我們先以來(lái)看看 表示元素對(duì)的Pair類型，可能有人一提到Pair類型馬上就會(huì)在腦海中浮現(xiàn)出下面的結(jié)構(gòu)：

  1. struct Pair { 
  2.     int left; 
  3.     int right; 
  4. } 

其實(shí)，這種理解是非本質(zhì)的，Pair完全可以用2個(gè)元素的數(shù)組來(lái)表示，第一個(gè)元素表示left，第二個(gè)元素表示right：

  1. struct Pair { 
  2.     int elements[2]; 
  3. } 

上面的兩種不同表示是類型的不同實(shí)現(xiàn)，而類型的本質(zhì)是由操作(Operation)和操作間的關(guān)系或不變式(Invariant)所定義的，我們稱之為類型規(guī)范(Type Specification)。比如，Pair類型是這樣定義的：

  1. Type Pair: 
  2.     Operations: 
  3.         Pair make_pair(int x, int y) 
  4.         int get_left(Pair pair) 
  5.         int get_right(Pair pair) 
  6.     Invariants: 
  7.         get_left(make_pair(x, y)) == x  //對(duì)x, y構(gòu)造的Pair取左元素等于x 
  8.         get_right(make_pair(x, y)) == y  //對(duì)x, y構(gòu)造的Pair取右元素等于y 

也就是說(shuō)只要是滿足Pair類型規(guī)范，即定義了make_pair，get_left, get_right這3種操作，并且這些操作滿足上面兩個(gè)不變式，那么它這就是Pair類型。我們?cè)賮?lái)看看稍微復(fù)雜一點(diǎn)的Stack類型：

  1. Type Stack: 
  2.     Operations: 
  3.         Stack make_stack()  //構(gòu)造空棧 
  4.         Stack push(Stack stack, int x)  //將元素x壓棧，返回新棧 
  5.         int top(stack)  //獲取棧頂元素 
  6.         Stack pop(Stack stack)  //將棧頂元素彈棧，返回新棧 
  7.     Invariants: 
  8.         top(push(stack, x)) == x  //棧頂元素為最后一次壓棧值 
  9.         pop(push(stack, x)) == stack  //對(duì)stack壓棧后再?gòu)棗５扔谠瓉?lái)的stack 

Stack類型規(guī)范簡(jiǎn)言之就是FILO（先入后出），如果要形式化就是上面的不變式。為了加深理解，我們現(xiàn)在切換到測(cè)試視角來(lái)看一看，如果請(qǐng)你來(lái)編 寫(xiě)一個(gè)Stack類的單元測(cè)試用例，你應(yīng)該怎么寫(xiě)呢？許多朋友都不清楚單元測(cè)試到底測(cè)什么？怎么測(cè)？我見(jiàn)過(guò)不少人用一個(gè)測(cè)試用例單獨(dú)對(duì)push做測(cè)試，用 另一個(gè)測(cè)試用例對(duì)pop單獨(dú)做測(cè)試，其主要原因就在于缺乏對(duì)類型本質(zhì)的理解。其實(shí)，只要理解了類型的本質(zhì)我們就知道孤立地看push或pop是沒(méi)有任何意 義的，它們的意義是在FILO關(guān)系下相互解釋的，所以測(cè)試當(dāng)然是基于類型規(guī)范來(lái)測(cè)試FILO不變式！這種基于類型規(guī)范的測(cè)試是一種黑盒測(cè)試，與類型的內(nèi)部 實(shí)現(xiàn)細(xì)節(jié)無(wú)關(guān)，只要單元測(cè)試覆蓋了類型所定義的所有操作和不變式，那么不管內(nèi)部怎么實(shí)現(xiàn)或優(yōu)化，測(cè)試用例都不需要調(diào)整。反之，如果深入到了類型的內(nèi)部實(shí)現(xiàn) 做白盒測(cè)試，那這樣的測(cè)試用例實(shí)際上就不再是反映其類型規(guī)范了，它會(huì)隨著實(shí)現(xiàn)細(xì)節(jié)的調(diào)整而失效。

更深一層來(lái)看，不僅是在Pair，Stack這樣的微觀層面，在一個(gè)系統(tǒng)的宏觀層面同樣可以采用類型視角，即考察系統(tǒng)定義了哪些操作？這些操作之間 有什么樣的關(guān)系或不變式？比如，你如何從類型的角度來(lái)看待MySQL這樣一套數(shù)據(jù)庫(kù)系統(tǒng)？MySQL系統(tǒng)定義了哪些操作？這些操作之間必須滿足怎樣的關(guān)系 和不變式？不僅如此，類型視角除了可以應(yīng)用于計(jì)算機(jī)系統(tǒng)，甚至還可以應(yīng)用于生活中的事物，比如，你到超市購(gòu)物可以寄存自己的包，在寄包的時(shí)候會(huì)獲得一張密 碼條，取包時(shí)可以通過(guò)密碼條打開(kāi)箱子。你能從超市寄包這個(gè)例子中看出類型來(lái)嗎？如果你看出來(lái)了，說(shuō)明你對(duì)類型的理解真正融會(huì)貫通了！

類型的函數(shù)式實(shí)現(xiàn)

上面我們介紹了類型的本質(zhì)在于操作和操作間的關(guān)系，下面我們要關(guān)注的是類型的實(shí)現(xiàn)。在上面的例子中，Pair的內(nèi)部結(jié)構(gòu)到底是什么，是一個(gè)left 和一個(gè)right成員？還是一個(gè)兩元素的數(shù)組？沒(méi)有講，也沒(méi)關(guān)系，就好像Windows的Handle和Linux的FileDescriptor一樣， 它們都是一個(gè)標(biāo)識(shí)，你并不需要關(guān)心它的值本身，你只需要用幾個(gè)相關(guān)的函數(shù)創(chuàng)建和操作它就行了（上面超市寄包例子中的密碼條和Windows中的 Handle是什么關(guān)系，你看出來(lái)了嗎？你需要理解密碼條的內(nèi)容嗎？）。換句話說(shuō)，只要滿足類型規(guī)范，具體實(shí)現(xiàn)是可變的，使用者只依賴于類型規(guī)范而不依賴于其具體實(shí)現(xiàn)。這在面向?qū)ο笳Z(yǔ)言中意味著接口保持不變而具體實(shí)現(xiàn)可以變化（這里把public方法視為一種廣義的接口）。

下面，我們還會(huì)看到的是不僅類型的內(nèi)部實(shí)現(xiàn)可以變化，而且可以根本沒(méi)有什么所謂的內(nèi)部實(shí)現(xiàn)。這是什么意思呢？讓我們來(lái)思考一下，是不是Pair內(nèi)部一定要有什么東西來(lái)保存構(gòu)造函數(shù)傳入的left和right？我們能跳出這個(gè)定勢(shì)嗎？在函數(shù)式編程中，我們能做到：

  1. //Javascript 
  2. function make_pair(x, y) { 
  3.     // 返回一個(gè)支持get_left和get_right操作的閉包(Closure) 
  4.     return { 
  5.         get_left : function() { return x }, 
  6.         get_right : function() { return y } 
  7.     } 
  8. } 
  9. function get_left(pair) { 
  10.     return pair.get_left(); 
  11. } 
  12. function get_right(pair) { 
  13.     return pair.get_right(); 
  14. } 
  15. // Test case 
  16. console.log(get_left(make_pair(1, 2))) //1 
  17. console.log(get_right(make_pair(1, 2))) //2 

#p#

上面的關(guān)鍵代碼在于make_pair的內(nèi)部返回的不是一種具體的數(shù)據(jù)結(jié)構(gòu)，而是一個(gè)支持get_left和get_right操作的閉包 (Closure)，將來(lái)可以通過(guò)get_left和get_right來(lái)提取x, y。這種基于閉包的實(shí)現(xiàn)和我們通常采用的基于數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)的本質(zhì)區(qū)別在哪里呢？不難發(fā)現(xiàn)，基于閉包的實(shí)現(xiàn)和類型規(guī)范是完全對(duì)應(yīng)的， 它并沒(méi)有引入類型規(guī)范之外的東西，而基于數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)則隱藏了實(shí)現(xiàn)的細(xì)節(jié)。換句話說(shuō)，如果要驗(yàn)證實(shí)現(xiàn)代碼的正確性，對(duì)于前者只需要比對(duì)著類型規(guī)范，對(duì)于 后者我們可能需要去仔細(xì)理解推敲其所采用的數(shù)據(jù)結(jié)構(gòu)。對(duì)于Pair這樣簡(jiǎn)單的結(jié)構(gòu)二者差別不大，甚至基于數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)更簡(jiǎn)單，但是對(duì)于復(fù)雜的類型就容易 體現(xiàn)出閉包實(shí)現(xiàn)的優(yōu)勢(shì)了。為了加深理解，我們?cè)賮?lái)看一個(gè)Stack的函數(shù)式實(shí)現(xiàn)：

  1. //Javascript 
  2. function make_stack() { 
  3.     return null 
  4. } 
  5. function push(stack, x) { 
  6.     return { 
  7.         top : function() { return x }, 
  8.         pop : function() { return stack } 
  9.     } 
  10. } 
  11. function top(stack) { 
  12.     return stack.top() 
  13. } 
  14. function pop(stack) { 
  15.     return stack.pop() 
  16. } 
  17. // Test case 
  18. var stack = make_stack() 
  19. stack = push(stack, 1) 
  20. stack = push(stack, 2) 
  21. stack = push(stack, 3) 
  22. console.log(top(stack)) //3 
  23. stack = pop(stack) 
  24. console.log(top(stack)) //2 
  25. stack = push(stack, 4) 
  26. console.log(top(stack)) //4 

上面的所有函數(shù)都是采用了無(wú)副作用的純函數(shù)式設(shè)計(jì)，可能習(xí)慣面向?qū)ο缶幊痰呐笥巡皇呛芰?xí)慣，不過(guò)這不影響我們對(duì)類型的討論，而且它也很容易改造成面向?qū)ο蟮娘L(fēng)格，感興趣的朋友可以自己嘗試對(duì)上面的代碼進(jìn)行簡(jiǎn)單的包裝讓它看起來(lái)像面向?qū)ο蟮臉幼印?/p>

函數(shù)式二叉樹(shù)迭代器

上面我們介紹了類型的本質(zhì)和函數(shù)式實(shí)現(xiàn)，下面我們?cè)賮?lái)看看Iterator類型又該如何定義和實(shí)現(xiàn)呢？ 思路當(dāng)然還是從操作入手，考慮Iterator類型對(duì)應(yīng)了哪些操作，它們的關(guān)系是什么？上面九瓜提示了Iterator類型可以抽象為線性表List類 型，或者說(shuō)Iterator本質(zhì)上是一個(gè)List。為什么呢？其實(shí)，只要跳出“如何表示數(shù)據(jù)結(jié)構(gòu)”的思維，從類型角度思考就很容易理解，因?yàn)?Iterator和List都定義了相同的操作，Iterator的使用者完全不關(guān)心也不知道它背后到底是鏈表還是二叉樹(shù)，你對(duì)Iterator的操作和 一個(gè)List的操作完全一樣。正是這個(gè)原因，STL等范型庫(kù)才能通過(guò)Iterator將算法和數(shù)據(jù)結(jié)構(gòu)解耦。

怎么定義一個(gè)List類型呢？九瓜提到的empty(), singleton()和append()實(shí)際上就是和List打交道最多的Lisp語(yǔ)言的經(jīng)典定義方式。Lisp是基于s-expression 的，s-expression既可以視為線性表又可以視為樹(shù)，本質(zhì)上Lisp為L(zhǎng)ist類型了構(gòu)造、取首元素和取剩余元素等幾種操作：

  1. Type List: 
  2.     Operations: 
  3.         List empty()  //構(gòu)造空表，通常由()這個(gè)文字量表示 
  4.         List singleton(Element e)  //構(gòu)造包含一個(gè)元素的表，通常由(e)這個(gè)文字量表示 
  5.         Element first(List list)   //取list的第一個(gè)元素，通常又叫car操作 
  6.         List rest(List list)  //取list除第一個(gè)元素外的剩余部分，通常又叫cdr操作 
  7.         List append(List list1, List list2) //連接兩個(gè)表 
  8.     Invariants: 
  9.         append(empty(), list) == list  //空表和表list連接后等于表list 
  10.         append(list, empty()) == list  //空表和表list連接后等于表list 
  11.         first(singleton(e)) == e  //對(duì)singleton(e)取首元素等于e 
  12.         rest(singleton(e)) == empty()  //對(duì)singleton(e)取首元素外的剩余部分的結(jié)果為空表 
  13.         append(first(list), rest(list)) == list  //對(duì)list的首尾兩部分進(jìn)行連接等于list本身 
  14.         if list1 is not empty then 
  15.             first(append(list1, list2)) == first(list1)  //對(duì)非空表list1于表list2的連接取首元素等于對(duì)非空表list1取首元素 
  16.         if list1 is not empty then 
  17.             rest(append(list1, list2)) == append(rest(list1), list2)  //對(duì)非空表list1于表list2的連接取首元素等于對(duì)非空表list1取首元素 

有了上面的分析，我們相應(yīng)地寫(xiě)出下面的List實(shí)現(xiàn)：

  1. //Javascript 
  2. function empty() { 
  3.     return null 
  4. } 
  5. function singleton(e) { 
  6.     return { 
  7.         first: function() { return e }, 
  8.         rest: function() { return null } 
  9.     } 
  10. } 
  11. function first(list) { 
  12.     return list.first() 
  13. } 
  14. function rest(list) { 
  15.     return list.rest() 
  16. } 
  17. function append(list1, list2) { 
  18.     if (null == list1) return list2 
  19.     if (null == list2) return list1 
  20.   
  21.     return { 
  22.         first : function() { return first(list1) }, 
  23.         rest : function() { return append(rest(list1), list2) } 
  24.     } 
  25. } 

#p#

在此基礎(chǔ)上可以進(jìn)一步實(shí)現(xiàn)二叉樹(shù)迭代器：

  1. function make_binary_tree_iterator(node) { 
  2.     return { 
  3.         first : function() { 
  4.             return null != node.left ? first(make_binary_tree_iterator(node.left)) : node 
  5.         }, 
  6.         rest : function() { 
  7.             var left_it = (null == node.left ? null : make_binary_tree_iterator(node.left)) 
  8.             var root_it = singleton(node) 
  9.             var right_it = (null == node.right ? null : make_binary_tree_iterator(node.right)) 
  10.             var it = append(append(left_it, root_it), right_it) 
  11.             return rest(it) 
  12.         } 
  13.     } 
  14. } 
  15. //======== Test case ======== 
  16. var tree = { 
  17.     value : 1, 
  18.         left : { 
  19.             value : 2, 
  20.             left : { value : 4, left : null, right : null }, 
  21.             right : null 
  22.         }, 
  23.         right : { 
  24.             value : 3, 
  25.             left : null, 
  26.             right : { value : 7, left : null, right : null } 
  27.     } 
  28. } 
  29. for (var it = make_binary_tree_iterator(tree); null != it; it = rest(it)) { 
  30.     console.log(first(it).value) 
  31. } 

上面的make_binary_tree_iterator在List類型的基礎(chǔ)上按照二叉樹(shù)遍歷過(guò)程構(gòu)造了一個(gè)List。不知道你是否注意到了，為什么它不像下面這個(gè)例子一樣直接返回一個(gè)List，而要構(gòu)造一個(gè)閉包呢？

  1. function make_binary_tree_iterator(node) { 
  2.     var left_it = (null == node.left ? null : make_binary_tree_iterator(node.left)) 
  3.     var root_it = singleton(node) 
  4.     var right_it = (null == node.right ? null : make_binary_tree_iterator(node.right)) 
  5.     return append(append(left_it, root_it), right_it) 
  6. } 

這里關(guān)鍵的區(qū)別在于閉包是惰性求值的，也就是說(shuō)只有當(dāng)真正開(kāi)始迭代遍歷的時(shí)候才會(huì)逐漸對(duì)各個(gè)函數(shù)進(jìn)行求值，而上面的函數(shù)遞歸調(diào)用是非惰性的，會(huì)從一開(kāi)始就把所有結(jié)點(diǎn)展開(kāi)成線性表。如果你對(duì)這一點(diǎn)還不能很好地理解，可以嘗試在各個(gè)函數(shù)中加log跟蹤函數(shù)的調(diào)用過(guò)程。

總結(jié)

本文介紹了類型的本質(zhì)在于它所定義的操作以及操作之間的關(guān)系和不變式。類型的實(shí)現(xiàn)關(guān)鍵在于滿足類型規(guī)范的要求，而具體實(shí)現(xiàn)是可以變化的，使用者和測(cè) 試用例都應(yīng)該只依賴于類型規(guī)范而不依賴于具體實(shí)現(xiàn)。函數(shù)式的類型實(shí)現(xiàn)往往和類型規(guī)范是直接對(duì)應(yīng)的，簡(jiǎn)單通用，但可能有性能問(wèn)題，而命令式的類型實(shí)現(xiàn)往往會(huì) 引入復(fù)雜的內(nèi)部數(shù)據(jù)結(jié)構(gòu)，但是其優(yōu)點(diǎn)是高效。這兩種實(shí)現(xiàn)并不是完全互斥的，有時(shí)候可以將二者相結(jié)合達(dá)到簡(jiǎn)單與高效的結(jié)合。

原文鏈接：http://coolshell.cn/articles/10169.html

責(zé)任編輯：陳四芳 來(lái)源： 酷殼網(wǎng)
類型函數(shù)式
相關(guān)推薦

2021-08-18 07:56:05

Typescript類型本質(zhì)

2023-05-06 07:27:47

2021-03-27 10:54:34

Python函數(shù)代碼

2012-12-13 10:58:41

IBMdW

2018-04-04 14:29:33

2009-08-27 16:22:58

interfaceabstract cl

2020-10-09 08:26:16

架構(gòu)

2020-05-26 21:17:28

函數(shù)式編程純函數(shù)

2020-05-26 16:27:58

函數(shù)孩子編程

2020-09-23 16:07:52

JavaScript函數(shù)柯里化

2023-03-20 08:14:11

PHP類型轉(zhuǎn)換

2010-03-11 11:10:14

Python函數(shù)式

2011-10-19 15:47:13

2012-03-21 09:30:11

ibmdw

2023-11-21 07:17:36

Reac函數(shù)組件

2009-11-23 09:34:05

WPF本質(zhì)

2021-08-12 10:38:58

安全分析數(shù)據(jù)安全網(wǎng)絡(luò)安全

2009-07-08 16:10:24

Scala簡(jiǎn)介面向?qū)ο?/a>函數(shù)式

2009-09-27 15:29:00

Scala講座面向?qū)ο?/a>Scala

2020-02-06 19:12:36

Java函數(shù)式編程編程語(yǔ)言
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)