因為函數語言程式設計和指令式程式設計太不一樣，導致命令式的資料結構大部分在函數語言程式設計中無法應用。比如在純函式式語言中是無法實現陣列的。因為禁止賦值導致修改陣列中一個元素就要複製整個陣列，效率非常低。而因為沒有陣列，所以也沒有雜湊表等基於陣列的資料結構。（常量陣列是可以實現的，但需要語法支援或用命令式語言寫的的庫。）函式式語言中應用最多的資料結構恐怕是列表（單向連結串列）。但即便是列表，使用上也有很多限制。比如往列表末尾新增新元素的操作需要複製整個列表……因為……這需要修改最後一項的next指標，又不能賦值，所以最後一項要複製；於是需要修改倒數第二項的next指標，於是倒數第二項要複製……這豈不是連個高效的佇列都無法實現吶……於是就有了函式式資料結構。在函數語言程式設計中，最簡單的佇列可以這樣實現的：準備兩個列表，分別叫head和tail。如果佇列是［1，2，3，4，5］，head和tail可以分別是［1，2，3］和［5，4］。push操作相當於對tail列表的cons操作，比如push 6之後使tail變成［6，5，4］。pop的時候取head裡的元素，當head用完的時候執行：head＝reverse tail，tail＝［］。這樣的話push和pop都只要O（1）就可以了。但這樣仍然效率不高啊，總有時候會執行reverse怎麼辦？對於實時性要求不高的程式，無視它就好了。因為當reverse的時候如果tail裡有n個元素，那一定執行了n次push操作，這樣的話平攤下來每次push導致的reverse時間增加是O（1）的，還可以接受。但對於實時性要求高的程式就需要各種最佳化減少每次reverse導致的停頓了。另外，惰性求值也會造成實時性降低。因為求值保證了那個值隨時可以取得，惰性求值卻使得最簡單的操作都無法預計其要花費多少時間。比如好不容易用二叉樹實現了一個高效的Map，卻絕望地發現實際使用的時候記憶體中存放的是insert k1 v1 $ insert k2 v2 $ insert k3 v3 ……本質上還是連結串列，只有第一次取k10000對應的值的時候才會把前10000個k-v pair插入到樹裡……所以函式式資料結構對於函數語言程式設計只是不得已才那麼做，效率肯定不及命令式。至於為什麼命令式的資料結構更高效，是因為我們用的計算機就是基於儲存器的，擁有很廉價的賦值操作，函數語言程式設計卻不能充分利用賦值。參考：Purely Functional Data Structures. Chris Okasaki. September 1996這本書還沒有看完，所以只能說這麼多了。
因為函數語言程式設計和指令式程式設計太不一樣，導致命令式的資料結構大部分在函數語言程式設計中無法應用。比如在純函式式語言中是無法實現陣列的。因為禁止賦值導致修改陣列中一個元素就要複製整個陣列，效率非常低。而因為沒有陣列，所以也沒有雜湊表等基於陣列的資料結構。（常量陣列是可以實現的，但需要語法支援或用命令式語言寫的的庫。）函式式語言中應用最多的資料結構恐怕是列表（單向連結串列）。但即便是列表，使用上也有很多限制。比如往列表末尾新增新元素的操作需要複製整個列表……因為……這需要修改最後一項的next指標，又不能賦值，所以最後一項要複製；於是需要修改倒數第二項的next指標，於是倒數第二項要複製……這豈不是連個高效的佇列都無法實現吶……於是就有了函式式資料結構。在函數語言程式設計中，最簡單的佇列可以這樣實現的：準備兩個列表，分別叫head和tail。如果佇列是［1，2，3，4，5］，head和tail可以分別是［1，2，3］和［5，4］。push操作相當於對tail列表的cons操作，比如push 6之後使tail變成［6，5，4］。pop的時候取head裡的元素，當head用完的時候執行：head＝reverse tail，tail＝［］。這樣的話push和pop都只要O（1）就可以了。但這樣仍然效率不高啊，總有時候會執行reverse怎麼辦？對於實時性要求不高的程式，無視它就好了。因為當reverse的時候如果tail裡有n個元素，那一定執行了n次push操作，這樣的話平攤下來每次push導致的reverse時間增加是O（1）的，還可以接受。但對於實時性要求高的程式就需要各種最佳化減少每次reverse導致的停頓了。另外，惰性求值也會造成實時性降低。因為求值保證了那個值隨時可以取得，惰性求值卻使得最簡單的操作都無法預計其要花費多少時間。比如好不容易用二叉樹實現了一個高效的Map，卻絕望地發現實際使用的時候記憶體中存放的是insert k1 v1 $ insert k2 v2 $ insert k3 v3 ……本質上還是連結串列，只有第一次取k10000對應的值的時候才會把前10000個k-v pair插入到樹裡……所以函式式資料結構對於函數語言程式設計只是不得已才那麼做，效率肯定不及命令式。至於為什麼命令式的資料結構更高效，是因為我們用的計算機就是基於儲存器的，擁有很廉價的賦值操作，函數語言程式設計卻不能充分利用賦值。參考：Purely Functional Data Structures. Chris Okasaki. September 1996這本書還沒有看完，所以只能說這麼多了。