常用資料結構簡短導覽
保證不會太長！
你現在可能已經對 Erlang 的函數式子集有相當的了解，並且可以毫無困難地閱讀許多程式。然而，我敢打賭，即使上一章是在講如何以函數式方法解決問題，你仍然很難思考如何建構一個真正有用的程式。我這麼說是因為這是我在學習到那個階段時的感受，但如果你表現得更好，恭喜你！
總之，我想說的是，我們已經看過很多東西：最基本的資料類型、shell、如何編寫模組和函數（使用遞迴）、不同的編譯方式、控制程式流程、處理例外、抽象化一些常見的操作等等。我們也看過如何使用 tuple、list 和一個不完整的二元搜尋樹來儲存資料。我們還沒看過的是 Erlang 標準函式庫中提供給程式設計師的其他資料結構。
記錄 (Records)
首先，記錄 (records) 是一種 hack。它們或多或少是語言的後加功能，可能會有一些不便之處。我稍後會提到這點。當你想要直接用名稱存取屬性的時候，它們對於小型資料結構還是相當有用的。因此，Erlang 的記錄很像 C 語言中的結構 (struct) (如果你了解 C 的話)。
它們以模組屬性的形式宣告，如下所示
-module(records).
-compile(export_all).
-record(robot, {name,
type=industrial,
hobbies,
details=[]}).
這裡我們有一個代表機器人的記錄，其中有 4 個欄位：name、type、hobbies 和 details。type 和 details 也有預設值，分別為 industrial 和 []。以下是在模組 records 中宣告記錄的方式
first_robot() ->
#robot{name="Mechatron",
type=handmade,
details=["Moved by a small man inside"]}.
然後執行程式碼
1> c(records).
{ok,records}
2> records:first_robot().
{robot,"Mechatron",handmade,undefined,
["Moved by a small man inside"]}
哎呀！hack 出現了！Erlang 記錄只是 tuple 之上的語法糖。幸好，有辦法讓情況更好。Erlang shell 有一個指令 rr(Module)，可讓你從 Module 載入記錄定義。
3> rr(records).
[robot]
4> records:first_robot().
#robot{name = "Mechatron",type = handmade,
hobbies = undefined,
details = ["Moved by a small man inside"]}
啊，這樣一來，用記錄處理事情就容易多了。你會注意到，在 first_robot/0 中，我們沒有定義 hobbies 欄位，而且它的宣告中沒有預設值。Erlang 預設會將值設為 undefined。
為了查看我們在 robot 定義中設定的預設值的行為，讓我們編譯以下函數
car_factory(CorpName) ->
#robot{name=CorpName, hobbies="building cars"}.
然後執行它
5> c(records).
{ok,records}
6> records:car_factory("Jokeswagen").
#robot{name = "Jokeswagen",type = industrial,
hobbies = "building cars",details = []}
我們就有了一個喜歡花時間組裝汽車的工業機器人。
注意： 函數 rr() 可以接收不只一個模組名稱：它可以接收萬用字元 (如 rr("*"))，也可以接收一個 list 作為第二個參數，以指定要載入哪些記錄。
shell 中還有一些其他處理記錄的函數：rd(Name, Definition) 可讓你用類似於模組中使用的 -record(Name, Definition) 的方式定義記錄。你可以使用 rf() 來「卸載」所有記錄，或使用 rf(Name) 或 rf([Names]) 來移除特定的定義。
你可以使用 rl() 列印所有記錄定義，其方式與你可以複製貼上到模組中的方式相同，也可以使用 rl(Name) 或 rl([Names]) 將其限制為特定記錄。
最後，rp(Term) 可讓你將 tuple 轉換為記錄 (如果定義存在的話)。
單單編寫記錄並不會有太多作用。我們需要一種從中提取值的方法。基本上有兩種方法可以做到這一點。第一種是使用特殊的「點語法」。假設你已載入機器人的記錄定義
5> Crusher = #robot{name="Crusher", hobbies=["Crushing people","petting cats"]}.
#robot{name = "Crusher",type = industrial,
hobbies = ["Crushing people","petting cats"],
details = []}
6> Crusher#robot.hobbies.
["Crushing people","petting cats"]
唉，這不是一個漂亮的語法。這是由於記錄作為 tuple 的本質所致。因為它們只是一些編譯器技巧，你必須保留一些關鍵字來定義哪個記錄對應哪個變數，因此有了 Crusher#robot.hobbies 中的 #robot 部分。很遺憾，這是無可避免的。更糟的是，巢狀記錄會變得非常醜陋
7> NestedBot = #robot{details=#robot{name="erNest"}}.
#robot{name = undefined,type = industrial,
hobbies = undefined,
details = #robot{name = "erNest",type = industrial,
hobbies = undefined,details = []}}
8> (NestedBot#robot.details)#robot.name.
"erNest"
沒錯，括號是必須的。
更新
從 R14A 修訂版開始，現在可以巢狀記錄，而無需括號。上面的 NestedBot 範例也可以寫成 NestedRobot#robot.details#robot.name，而且效果相同。
為了進一步顯示記錄對 tuple 的依賴性，請參閱以下內容
9> #robot.type. 3
這會輸出它在底層 tuple 中的哪個元素。
記錄的一個省力功能是可以在函數頭中使用它們進行模式匹配，也可以在 guard 中使用。在檔案頂端宣告一個新的記錄，如下所示，然後在下面新增函數
-record(user, {id, name, group, age}).
%% use pattern matching to filter
admin_panel(#user{name=Name, group=admin}) ->
Name ++ " is allowed!";
admin_panel(#user{name=Name}) ->
Name ++ " is not allowed".
%% can extend user without problem
adult_section(U = #user{}) when U#user.age >= 18 ->
%% Show stuff that can't be written in such a text
allowed;
adult_section(_) ->
%% redirect to sesame street site
forbidden.
在 admin_panel/1 函數中示範了將變數繫結到記錄的任何欄位的語法（可以將變數繫結到多個欄位）。關於 adult_section/1 函數要注意的重要一點是，你需要執行 SomeVar = #some_record{} 才能將整個記錄繫結到變數。然後我們照常編譯
10> c(records).
{ok,records}
11> rr(records).
[robot,user]
12> records:admin_panel(#user{id=1, name="ferd", group=admin, age=96}).
"ferd is allowed!"
13> records:admin_panel(#user{id=2, name="you", group=users, age=66}).
"you is not allowed"
14> records:adult_section(#user{id=21, name="Bill", group=users, age=72}).
allowed
15> records:adult_section(#user{id=22, name="Noah", group=users, age=13}).
forbidden
這讓我們看到，在編寫函數時，不必匹配 tuple 的所有部分，甚至不必知道有多少部分：我們只需要匹配年齡或群組，如果需要的話，而忽略結構的其餘部分。如果我們使用一般的 tuple，函數定義可能看起來像 function({record, _, _, ICareAboutThis, _, _}) -> ...。然後，每當有人決定在 tuple 中新增一個元素時，其他人（可能因此而感到惱火）就需要去更新所有使用該 tuple 的函數。
以下函數說明如何更新記錄 (否則它們不會很有用)
repairman(Rob) ->
Details = Rob#robot.details,
NewRob = Rob#robot{details=["Repaired by repairman"|Details]},
{repaired, NewRob}.
然後
16> c(records).
{ok,records}
17> records:repairman(#robot{name="Ulbert", hobbies=["trying to have feelings"]}).
{repaired,#robot{name = "Ulbert",type = industrial,
hobbies = ["trying to have feelings"],
details = ["Repaired by repairman"]}}
你可以看到我的機器人已修復。更新記錄的語法在這裡有點特殊。看起來我們是在原地更新記錄 (Rob#robot{Field=NewValue})，但這一切都是編譯器的把戲，用來呼叫底層的 erlang:setelement/3 函數。
關於記錄的最後一件事。因為它們非常有用，而且程式碼重複很麻煩，所以 Erlang 程式設計師經常借助標頭檔在各個模組之間共用記錄。Erlang 標頭檔與 C 語言的對應項目非常相似：它們只是一段程式碼，會被新增到模組中，就好像它們是直接寫在那裡的一樣。建立一個名為 records.hrl 的檔案，其中包含以下內容
%% this is a .hrl (header) file.
-record(included, {some_field,
some_default = "yeah!",
unimaginative_name}).
若要將其包含在 records.erl 中，只需將以下這一行新增到模組中
-include("records.hrl").
然後新增以下函數來試試看
included() -> #included{some_field="Some value"}.
現在，照常嘗試執行它
18> c(records).
{ok,records}
19> rr(records).
[included,robot,user]
20> records:included().
#included{some_field = "Some value",some_default = "yeah!",
unimaginative_name = undefined}
萬歲！關於記錄就到此為止了；它們很醜但很有用。它們的語法並不漂亮，它們不是什麼了不起的東西，只是一種 hack，但它們對於程式碼的可維護性相當重要。
注意： 你經常會看到開源軟體使用這裡顯示的方法，為所有模組共用的記錄建立一個專案範圍的 .hrl 檔案。雖然我覺得有義務記錄這種用法，但我強烈建議你將所有記錄定義保留在本地，在一個模組內。如果你想要讓其他模組查看記錄的內部結構，請編寫函數來存取其欄位，並儘可能保持其詳細資訊的私密性。這有助於防止名稱衝突、避免升級程式碼時發生問題，並大致改善程式碼的可讀性和可維護性。
鍵值儲存
我在前幾章讓你建構一個樹，而其用途是將它用作通訊錄的鍵值儲存。那本通訊錄很糟糕：我們無法刪除或將其轉換為任何有用的東西。這是遞迴的一個很好的示範，但僅此而已。現在是時候向你介紹一些有用的資料結構和模組，以將資料儲存在特定鍵之下。我不會定義每個函數的作用，也不會瀏覽所有模組。我只會連結到文件頁面。把我當成某個負責「提高對 Erlang 中鍵值儲存的認識」的人，或類似的人。這聽起來是個好頭銜。我只需要其中一個緞帶。
對於少量資料，基本上可以使用兩種資料結構。第一種稱為 proplist。proplist 是任何形式為 [{Key,Value}] 的 tuple 的 list。它們是一種奇怪的結構，因為沒有其他規則。事實上，規則非常寬鬆，以至於 list 也可以包含布林值、整數和你想要的任何東西。不過，我們比較感興趣的是 list 中帶有鍵和值的 tuple 的概念。若要使用 proplist，可以使用 proplists 模組。它包含諸如 proplists:delete/2、proplists:get_value/2、proplists:get_all_values/2、proplists:lookup/2 和 proplists:lookup_all/2 等函數。
你會注意到沒有函數可以新增或更新 list 的元素。這顯示出 proplist 作為資料結構的定義有多鬆散。若要取得這些功能，你必須手動 cons 你的元素 ([NewElement|OldList])，並使用諸如 lists:keyreplace/4 等函數。為一個小型資料結構使用兩個模組並不是最乾淨的做法，但由於 proplist 的定義非常鬆散，因此它們經常被用來處理組態 list 以及給定項目的常規描述。proplist 並不是完全的資料結構。它們更像是在使用 list 和 tuple 來表示某些物件或項目時出現的常見模式；proplist 模組有點像這種模式的工具箱。
如果你確實想要一個更完整的鍵值儲存來儲存少量資料，那麼你需要的是 orddict 模組。Orddict (有序字典) 是具有形式感的 proplist。每個鍵只能出現一次，整個 list 會排序以加快平均查找速度等等。orddict:store/3、orddict:find/2 (當你不知道鍵是否在字典中時)、orddict:fetch/2 (當你知道它在那裡，或者它必須在那裡時) 和 orddict:erase/2 是CRUD使用中的常用函數。
Orddict 通常是在複雜性和效率之間取得良好平衡的方案，適用於約 75 個元素 (請參閱我的基準測試)。超過該數量後，你應該切換到不同的鍵值儲存。
基本上，有兩種主要的鍵值結構/模組用於處理大量資料：dicts 和 gb_trees。字典（Dictionaries）與 orddicts 有相同的介面：dict:store/3、dict:find/2、dict:fetch/2、dict:erase/2 以及其他所有函式，例如 dict:map/2 和 dict:fold/2 （對整個資料結構進行操作非常有用！）。因此，當需要擴展 orddicts 時，Dicts 是非常好的選擇。
另一方面，一般平衡樹（General Balanced Trees）具有更多函式，可讓您更直接地控制結構的使用方式。gb_trees 基本上有兩種模式：一種是您對結構瞭如指掌的模式（我稱之為「智慧模式」），另一種是您無法對其做出太多假設的模式（我稱之為「樸素模式」）。在樸素模式下，函式為 gb_trees:enter/3、gb_trees:lookup/2 和 gb_trees:delete_any/2。相關的智慧函式是 gb_trees:insert/3、gb_trees:get/2、gb_trees:update/3 和 gb_trees:delete/2。還有 gb_trees:map/2，當您需要它時，它總是一個不錯的功能。
「樸素」函式相較於「智慧」函式的缺點是，由於 gb_trees 是平衡樹，因此每當您插入新元素（或刪除一堆元素）時，樹可能需要自行平衡。這可能會花費時間和記憶體（即使是在無用的檢查中，僅為了確保）。「智慧」函式都假設鍵存在於樹中：這可以讓您跳過所有安全檢查，並縮短時間。
何時應該使用 gb_trees 而不是 dicts？嗯，這並不是一個明確的決定。正如我編寫的 基準測試模組 所顯示的，gb_trees 和 dicts 在許多方面都有相似的效能。但是，基準測試表明 dicts 具有最佳的讀取速度，而 gb_trees 在其他操作上往往會快一點。您可以根據自己的需求判斷哪個是最佳選擇。
另外請注意，雖然 dicts 有 fold 函式，但 gb_trees 沒有：它們反而有一個迭代器函式，該函式返回樹的一部分，您可以在其上呼叫 gb_trees:next(Iterator) 以按順序取得後續值。這表示您需要在 gb_trees 之上編寫自己的遞迴函式，而不是使用通用的 fold。另一方面，gb_trees 可讓您使用 gb_trees:smallest/1 和 gb_trees:largest/1 快速存取結構的最小和最大元素。
因此，我會說，您應用程式的需求應該決定要選擇哪個鍵值儲存。諸如您必須儲存多少資料、需要對其執行什麼操作等等的不同因素都具有其重要性。進行衡量、分析和基準測試以確保。
注意：存在一些特殊的鍵值儲存，用於處理不同大小的資源。此類儲存是 ETS 表格、DETS 表格和 mnesia 資料庫。但是，它們的使用與多個進程和分散的概念密切相關。因此，它們只會在稍後才被介紹。我將此作為參考，以激發您的好奇心，並為那些感興趣的人提供參考。
更新
從 17.0 版開始，該語言支援一種新的原生鍵值資料類型，詳見 附錄：Maps。它們應該是取代 dict 的新事實標準。
陣列
但是，如果程式碼需要僅包含數值鍵的資料結構呢？那麼，可以使用 陣列。它們允許您使用數值索引存取元素，並在整個結構上進行 fold 操作，同時可能會忽略未定義的插槽。
不要喝太多酷愛飲
與命令式語言中的陣列相反，Erlang 陣列無法擁有常數時間的插入或查找等功能。由於它們通常比支援破壞性賦值的語言中的陣列慢，而且使用 Erlang 進行程式設計的風格不一定很適合陣列和矩陣，因此它們在實務中很少使用。
通常，需要進行矩陣操作和其他需要陣列的 Erlang 程式設計師傾向於使用稱為 埠 的概念，讓其他語言進行繁重的工作，或使用 C-節點、連結的驅動程式和 NIF（實驗性，R13B03+）。
陣列也很奇怪，因為它們是少數幾個從 0 開始索引的資料結構之一（與元組或列表相反），就像 正規表示式模組中的索引一樣。小心使用它們。
集合的集合
如果您曾經在任何數學課中學習過集合論，您就會知道集合可以做什麼。如果您沒有，您可能想跳過這一部分。但是，我只想說，集合是您可以比較和操作的唯一元素組：找出哪些元素在兩個組中，哪些元素在其中一個組中，哪些元素只在其中一個組中等等。還有更多進階操作，可讓您定義關係並對這些關係進行操作等等。我不打算深入探討理論（同樣，這超出了本書的範圍），因此我將僅描述它們的現狀。
在 Erlang 中，有 4 個主要模組用於處理集合。這乍看之下有點奇怪，但是一旦您意識到這是因為實作者一致認為沒有「最佳」的集合建構方式，就會更有意義。這四個模組是 ordsets、sets、gb_sets 和 sofs（集合的集合）。
- ordsets
- Ordsets 實作為排序列表。它們主要用於小型集合，是速度最慢的集合類型，但它們具有所有集合中最簡單且最易讀的表示形式。它們有標準函式，例如
ordsets:new/0、ordsets:is_element/2、ordsets:add_element/2、ordsets:del_element/2、ordsets:union/1、ordsets:intersection/1以及更多函式。 - sets
- Sets（模組）是建立在與
dict中使用的結構非常相似的結構之上。它們實作與 ordsets 相同的介面，但它們的可擴展性會好得多。與字典一樣，它們特別適合讀取密集型操作，例如檢查某個元素是否屬於集合的一部分。 - gb_sets
- Gb_sets 本身是建立在與 gb_trees 模組中使用的結構類似的一般平衡樹結構之上。gb_sets 對於 sets 來說，就像 gb_tree 對於 dict 一樣；當考慮到讀取以外的操作時，是一種更快的實作方式，讓您擁有更多的控制權。雖然 gb_sets 實作與 sets 和 ordsets 相同的介面，但它們還添加了更多函式。與 gb_trees 一樣，您有智慧與樸素的函式、迭代器、快速存取最小值和最大值等等。
- sofs
- 集合的集合 (sofs) 是使用排序列表實作的，排序列表會與某些中繼資料一起放入元組中。如果您想要完全控制集合、族群之間的關係、強制執行集合類型等等，那麼可以使用此模組。如果您需要的是數學概念，而不僅僅是「單純的」唯一元素組，那麼這才是您真正需要的。
不要喝太多酷愛飲
雖然這種多樣性可以被視為很棒的事情，但某些實作細節可能會讓人感到非常沮喪。舉例來說，gb_sets、ordsets 和 sofs 都使用 == 運算子來比較值：如果您有數字 2 和 2.0，它們最終都會被視為同一個。
但是，sets（模組）使用 =:= 運算子，這表示您不一定可以隨意切換到每個實作。在某些情況下，您需要一種精確的行為，而在這種情況下，您可能會失去擁有多種實作的好處。
有這麼多選項可以使用，的確有點令人困惑。來自 Erlang/OTP 團隊，同時也是 Wings3D 的程式設計師 Björn Gustavsson 主要建議在大多數情況下使用 gb_sets，當你需要一個清晰的表示，以便用自己的程式碼處理時使用 ordset，而當你需要 =:= 運算子時則使用 'sets'（來源）。
無論如何，就像鍵值儲存一樣，最好的解決方案通常是進行基準測試，看看哪種更適合您的應用程式。
有向圖
這裡我想提及另一種資料結構（並不是說這一章節中提到的就只有這些，恰恰相反）：有向圖。同樣地，這個資料結構比較適合已經了解相關數學理論的讀者。
Erlang 中的有向圖是以兩個模組實作的，分別是 digraph 和 digraph_utils。digraph 模組基本上允許建構和修改有向圖：處理邊和頂點、尋找路徑和環等等。另一方面，digraph_utils 允許您導覽圖（後序、前序）、測試環、樹狀結構或樹、尋找鄰居等等。
因為有向圖與集合論密切相關，所以 'sofs' 模組包含一些函數，可讓您將族轉換為有向圖以及將有向圖轉換為族。
佇列
它們的實作方式有點像上面說明的：兩個列表（在這個上下文中是堆疊），允許快速附加和前置元素。
queue 模組基本上有不同的函數，心智上分為 3 個不同複雜程度的介面（或 API），稱為「原始 API」、「擴充 API」和「Okasaki API」。
- 原始 API
- 原始 API 包含佇列概念的基本函數，包括：
new/0，用於建立空佇列；in/2，用於插入新元素；out/1，用於移除元素；然後還有轉換為列表、反轉佇列、查看特定值是否為佇列的一部分等等的函數。 - 擴充 API
- 擴充 API 主要增加了一些內省能力和彈性：它允許您執行諸如查看佇列前端而無需移除第一個元素的操作（請參閱
get/1或peek/1）、移除元素而無需關心它們（drop/1）等等。這些函數對於佇列的概念來說不是必需的，但它們在一般情況下仍然有用。 - Okasaki API
- Okasaki API 有點奇怪。它源自 Chris Okasaki 的純函數式資料結構。該 API 提供的操作與前兩個 API 中提供的操作類似，但是某些函數名稱是反向書寫的，並且整個 API 相對特殊。除非您知道自己需要此 API，否則我不會理會它。
通常，當您需要確保第一個排序的項目確實是第一個處理的項目時，您會想使用佇列。到目前為止，我展示的範例主要使用列表作為累積器，然後將其反轉。在您無法一次執行所有反轉並且經常新增元素的情況下，您需要使用佇列模組（好吧，您應該先測試和測量！始終先測試和測量！）
簡短旅程結束
這就是 Erlang 資料結構之旅的全部內容。感謝您一路將您的手臂放在車內。當然，還有更多的資料結構可用於解決不同的問題。我僅涵蓋了您最有可能遇到或最需要的那些，因為它們是一般 Erlang 使用案例中的優勢。我鼓勵您探索標準函式庫和擴充函式庫，以查找更多資訊。
您可能會很高興得知這結束了我們進入循序（函數式）Erlang 的旅程。我知道很多人進入 Erlang 是為了了解所有並行和進程等等。這是可以理解的，因為這確實是 Erlang 的優勢所在。監督樹、精緻的錯誤管理、分散式等等。我知道我一直很迫不及待地想寫這些主題，所以我猜一些讀者也很迫不及待地想閱讀它們。
但是，我認為在轉向並行 Erlang 之前，先熟悉函數式 Erlang 會更有意義。之後更容易繼續前進，並專注於所有新概念。我們開始吧！
