原視頻鏈接：https://www.youtube.com/watch?v=Wo0qiGPSV-s by Anjana Vakil@JSConf

成都創新互聯專業為企業提供突泉網站建設、突泉做網站、突泉網站設計、突泉網站制作等企業網站建設、網頁設計與制作、突泉企業網站模板建站服務，10年突泉做網站經驗，不只是建網站，更提供有價值的思路和整體網絡服務。

概述

　　函數式編程避免了很多命令式和面向對象的編程的問題。

　　在函數中，數據輸入，數據輸出和數據轉換就是這個函數的目的功能。

　　與之緊密相連的，就是要避免可變性帶來的副作用。所以，不變性在這里就顯得很酷。

　　假如我們有一個數組zoo，里面存放著一排數據。依次存放猴子、兔子、熊貓、狗熊、章魚、青蛙、老虎、考拉這八個動物。而我們需要用外星人取代兔子的位置。如果直接把外星人替代兔子的位置則改變了整個數組，即觸發了可變性。通常的解決辦法是，將原數組zoo復制成一個新數組newZoo。再將里面的兔子替換成外星人。這樣即能避免觸發可變性。但不可忽略的是，當原數組越大，這一過程會占用大量的時間和空間。copying wastes time / space。因此，如果要實現不變性，我們必須找到更好的方法。

解決方案

關于有效地實現不變性的解決方案：

1. 不變的數據結構！like rock，just sit.
2. 持久數據結構！

　　　 持久數據能訪問其舊版本的數據。因此，我們一直在創建新的修改版本的同時保留了舊版本。部分持久性數據結構使我們可以訪問它們，但不能返回并更新其中任何數據，我們只能修改最新版本。還有完全持久性數據結構，我們可以回去更新任何過去的版本，it's version control like git.

　　我們將這些統稱為持久不可變數據結構，特點是持久且不變。so，what should we do？

　　所有的這些關鍵是，我們想要舊的數據版本，例如上面提到的原始數組zoo，我們只是想讓它保持不變，like rock. 但同時又能有效地創建新版本。所以，Trees and sharing （樹結構和共享）來拯救我們了。

　　想象一下，將我們的數組zoo表示為一棵樹，每片葉子擁有一個值，一只動物。讓我們把它們每兩個放在一起。like this：

結構不斷上升，現在得到根是一個表示為一棵樹的數組：

　　基于這種數據結構，我們如何來更新我們的數據？（用外星人來替換兔子的位置）

　　鑒于我的數據是永遠不變的，所以在這里我們要做的是，先找出我要更改的節點；然后創建一個副本，兔子換成了外星人；再然后需要復制所有指向該節點之上的中間層節點；相當于基本上找到一條通往根的路徑，且有了新的根 called new ：

表示數據的另一個版本。這種復制從葉子到根節點的做法稱為 路徑復制（path copying）。如今我們沒有復制整個數組，只需要復制從根到我改變的葉子之間的節點。因此，時間復雜度從 O(N) 變成 O(logN) ，性能更高，that's pretty cool.

　　黃色部分的節點在兩個版本之間共享。因此，內存的消耗變小了，因為可以重用原始的部分，且不必復制沒有改變的東西。這就是所謂的結構變更，共享樹的結構在兩個版本之間。

　　事實證明這是一種叫做 TRIE（來自“retrieval”-- 檢索） 的特殊樹結構。

　　TRIE 是一種樹，葉子代表值，到達葉子節點的路徑是值相關的鍵值。我們可以將二進制數作為索引，我們可以 bit-by-bit 逐漸查找樹，for example（找索引為 5 的青蛙）：

　　At the same time, 當索引值很大的時候，like zoo[ ] 則對應 zoo[ 0b ] ，意味著這將是一棵非常深的樹，有 15 層。因此，在每個層級建立更多的分支，比如我們可以將其分成 5 位，zoo -> -> -> 00001，則只有 3 層分支。這是樹的深度與廣度之間的取舍。研究發現 32 在深度和廣度之間是一個很好的權衡。

　　當我們希望非整數作為鍵，應該怎么做？

　　它不再是數組，而是對象。like M for monkey and P for panda。此處 鍵 是字符串。Broaden your mind，哈希表！因此，如果我想查找 “M”關聯的值，我們可以對“M”進行哈希處理，得到數字索引。So，我們根據鍵的二進制表示搜索樹，使用了哈希函數把任意對象轉換成一個數字（即索引值）。

　　綜上，可變性讓人頭疼，函數式編程時尤其要避免。因為函數式編程就是關于避免副作用，只使用純函數。

純函數除了計算輸入輸出之外不改變任何東西，而且不變性很好。