函數式語言在狀態變換下如何工作

Question

我想知道函數式語言如何實現Vector的新狀態「引擎蓋下」的創建。當我有一個向量，並且向該特定向量添加另一個元素時，舊向量仍舊保持不變，並且包含舊元素的新向量被創建爲包含多個元素。

這是如何處理內部？有人可以試圖解釋它嗎？謝謝。

Answer 1

從概念上講，每次向量擴展或修改時都會創建一個新的向量。但是，由於原始矢量未被修改，所以可以使用巧妙的技術來共享結構。例如，請參閱ropes。

另請參閱岡崎的Purely Functional Data Structures.

Answer 2

如果將一個元素添加到鏈接列表中，則會創建一個新鏈接列表，並將新元素作爲其頭部，並將指向舊列表的指針作爲其尾部。

如果您將一個項目添加到數組中，通常會複製整個數組（通常會增量構建不可變數組效率非常低）。

但是如果你只添加到每個數組的末尾一次，像這樣：

arr1 = emptyArray() 
arr2 = add(arr1, 1) 
arr3 = add(arr2, 2) 
arr4 = add(arr3, 3) 

整個事情可以進行優化，從而使ARR1，ARR2，ARR3和arr4，都指向同一個記憶，但長度不同。當然，只有在您第一次添加到任何給定數組時，才能執行此優化。如果您有arr5 = add(arr4, 4)和arr5prime = add(arr4, 42)其中至少有一個需要是副本。

請注意，這不是一個常見的優化，所以除非在文檔中明確指出，否則不應該指望它在那裏。