原視頻鏈接：https://www.youtube.com/watch?v=Wo0qiGPSV-s by Anjana Vakil@JSConf 概述 函數式編程避免了很多命令式和麵向對象的編程的問題。 在函數中，數據輸入，數據輸出和數據轉換就是這個函數的目的功能。 與之緊密相連的，就是要避免可變性 ...
原視頻鏈接：https://www.youtube.com/watch?v=Wo0qiGPSV-s by Anjana Vakil@JSConf
概述
函數式編程避免了很多命令式和麵向對象的編程的問題。
在函數中，數據輸入，數據輸出和數據轉換就是這個函數的目的功能。
與之緊密相連的，就是要避免可變性帶來的副作用。所以，不變性在這裡就顯得很酷。
假如我們有一個數組zoo，裡面存放著一排數據。依次存放猴子、兔子、熊貓、狗熊、章魚、青蛙、老虎、考拉這八個動物。而我們需要用外星人取代兔子的位置。如果直接把外星人替代兔子的位置則改變了整個數組，即觸發了可變性。通常的解決辦法是，將原數組zoo複製成一個新數組newZoo。再將裡面的兔子替換成外星人。這樣即能避免觸發可變性。但不可忽略的是，當原數組越大，這一過程會占用大量的時間和空間。copying wastes time / space。因此，如果要實現不變性，我們必須找到更好的方法。
解決方案
關於有效地實現不變性的解決方案：
- 不變的數據結構！like rock，just sit.
- 持久數據結構！
持久數據能訪問其舊版本的數據。因此，我們一直在創建新的修改版本的同時保留了舊版本。部分持久性數據結構使我們可以訪問它們，但不能返回並更新其中任何數據，我們只能修改最新版本。還有完全持久性數據結構，我們可以回去更新任何過去的版本，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[ 18977 ] 則對應 zoo[ 0b10001000100001 ] ，意味著這將是一棵非常深的樹，有 15 層。因此，在每個層級建立更多的分支，比如我們可以將其分成 5 位，zoo -> 10010 -> 10001 -> 00001，則只有 3 層分支。這是樹的深度與廣度之間的取捨。研究發現 32 在深度和廣度之間是一個很好的權衡。
當我們希望非整數作為鍵，應該怎麼做？
它不再是數組，而是對象。like M for monkey and P for panda。此處 鍵 是字元串。Broaden your mind，哈希表！因此，如果我想查找 “M”關聯的值，我們可以對“M”進行哈希處理，得到數字索引。So，我們根據鍵的二進位表示搜索樹，使用了哈希函數把任意對象轉換成一個數字（即索引值）。
綜上，可變性讓人頭疼，函數式編程時尤其要避免。因為函數式編程就是關於避免副作用，只使用純函數。
純函數除了計算輸入輸出之外不改變任何東西，而且不變性很好。
在 Javascript 中，有一些很棒的庫可以幫助我們使用這些數據結構。如：
- Mori
Mori基本上是Clojure Script 的移植，作者是David Nolan。這些數據結構的實現來自Clojure Script 把 Clojure 編譯成原生 JavaScript。它的API是函數式的。
- Immutable.js
Facebook推出，由Lee Byron 創建。這是一個JavaScript實現的數據結構。儘管它返回的是新版本的數據結構，而不是原位改變數據。
它不是數組，是一個JS列表
兩者區別：
感謝您的閱讀，文章中如有敘述不恰當的地方望不吝賜教。
