Scheme語言中的「不可變數據」會產生性能問題嗎？

01-02

既然函數式編程語言一個特點是「不可變數據」，那麼函數傳參時和遍歷list或是map時是否會導致大量數據複製而產生性能問題？如果是，set!的出現是不是為了彌補這一問題？

Racket的Lists才是默認immutable的，所以它沒有set-car!和set-cdr!

append等操作的複雜度和List內部實現有關，通常(append a b)的複雜度是O(n)，n是a的長度，把a全複製一遍得到新列表。雖然不能「就地更新」，但是新、舊數據可以共享部分結構（此例中為b）。

類似(fun1 (fun2 (fun3 lst)))的以及高階函數、函數組合中，確實可能導致lst元素被複制多次，Haskell等語言有fusion等優化，immutable正是類似優化的基礎。

另：各種對List的改進主要是利用其他結構（樹、隊列、堆等）實現List，如Random Access List的nth可以實現O(log n)，Catenable List的append是O(1)..

總結：有些問題和imutalbe/mutalbe無關；immutable的實現有考量，不會無腦複製；immutable會有性能問題，也利於某些優化。

不要總覺得你寫了複製的代碼他就真的會複製，其實大部分的複製都是不會產生的。

immutable本身不會產生性能上的問題，更多是取決於你的實現比如在SML中

fun rev [] = [] | rev (x::xs) = (rev xs) @ [x];

就比

fun rev2 ([], ys) = ys | rev2 (x::xs, ys) = rev2 (xs, x::ys)

要慢，前者是O(n^2)，後者是O(n)的。

關於mutable和immutable，我們可以簡單從append進行比較

這是命令式語言中的做法，我們簡單的改變xs的尾指針將xs與ys連接成zs，這個操作時間複雜度是O(1)的，雖然高效，但是我們失去了原有的xs與ys，因此我們在需要使用xs和ys時得重新構建。

這種是函數式語言的做法，我們copy了xs中的節點，將它尾指針指向到ys，時間複雜度是O(n)，比前面的慢點，但是我們沒有破壞原有的xs和ys，並且我們不用copy ys中的節點，而是將它們與新的zs共享。

PS: PFDS提到append有一個O(1)實現，不過我還沒看到。

函數式編程語言不一定「不可變數據」，Scheme也不是所謂函數式編程語言，實現得好的Scheme沒有性能問題，普通list和map遍歷傳「引用」不複製「大量數據」，現有實現無法滿足需要的性能時可以用C、C++、Java，非要用Scheme可以自己用低級語言擴展自己的Scheme實現，set!解決的是別的問題。

如果頻繁修改容器內容，卻不頻繁追加新元素，避免大量數據複製，可以用 scheme的 vector，沒人逼著你必須用 list，比如：

(define x (vector 1 2 3 4)) ; 定義一維數組 (vector-set! x 1 100) ; 修改 1位置的元素 (display x) (newline) (define y (vector (vector 1 2) (vector 3 4))) ; 定義二維數組 (list-&>vector a) ; 類型轉換 (vector-&>list x) ; 類型轉換

而且 vector在內存空間裡面是連續的，list是離散的，seek操作 vector是 O(1), list是 O(n)

再者，如果頻繁 append 新元素，一般情況下，不要往list尾部 append，而是頭部追加，比如x為 (3 2 1)，那麼 (cons 4 x) 就能得到 (4 3 2 1)，這是 O(1)的操作，然後你還可以倒過來方便遍歷（看具體遍歷的方向）。

---

一般來說：會，但不是很嚴重

因為

01 當一個值只作為一個函數的參數時，調用並不會複製，而是直接傳遞引用

02 當修改列表末尾的元素時開銷最大，因此這種場合常常使用樹來代替表

03 某些大開銷的操作，比如append兩個表，會被改成右結合

但是，有時候不可變數據開銷會更低，原因在於gc

因為很多時候變更數據，gc都會做一個原子操作，若是變更將一個次堆被主堆對象所引用，那麼將對其進行登記，這個操作是有開銷的，當此類操作數量大到一定程度的時候，性能還不如複製新的對象

最後，從scheme的角度來看，set! 可能不是為了改進性能，而是為了讓scheme在語義上更完整

都不可變了還複製個毛啊，複製是因為可變才會需要的保護動作。

用mutable才容易出現性能問題。

copy一個imutable又不是真的全部複製

scheme里的list壓根就不是不可變的，你可以用set-car!

函數傳參怎麼會複製。

函數式風格的操作是創建新的list而不是複製。

就算是我大C++還有copy-on-write的collection實現呢【逃

有沒有性能問題，要看實現，比如傳參時，Scheme標準沒規定是傳對象抑或傳引用，傳引用性能好，而且如果是不可變值的，相當於C++裡面的const T，無後顧之憂，此時不可變是反而是優點。還有map時亦可用惰性求值來避免遍歷，類似於C++的迭代器效果，此時不可變也是優點，因爲不用害怕迭代器失效。