常见数据结构的简短访问
不会太久，保证！
你可能已经很好地理解了 Erlang 的函数式子集，可以阅读很多程序而没有任何问题。但是，我敢打赌，尽管上一章是关于以函数式的方式解决问题，但你仍然难以思考如何构建一个真正实用的程序。我这么说，是因为在我学习的这段时间里，我也有这种感觉。不过，如果你做得更好，恭喜你！
总之，我要说的是，我们已经学习了很多东西：最基本的数据类型、Shell、如何编写模块和函数（使用递归）、不同的编译方式、控制程序流程、处理异常、抽象化一些常见的操作等等。我们还看到了如何使用元组、列表和一个不完整的二叉搜索树实现来存储数据。我们没有看到的，是 Erlang 标准库中提供给程序员的其他数据结构。
记录
首先，记录是一个 hack。它们或多或少是语言的“事后诸葛亮”，可能会带来一些不便。我将在后面介绍这些问题。当你要创建一个小的数据结构，并且希望通过名称直接访问属性时，它们仍然非常有用。因此，Erlang 记录很像 C 语言中的结构体（如果你了解 C 语言的话）。
它们以以下方式声明为模块属性
-module(records).
-compile(export_all).
-record(robot, {name,
type=industrial,
hobbies,
details=[]}).
因此，这里有一个代表机器人的记录，包含 4 个字段：名称、类型、爱好和详细信息。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 记录只是元组之上的语法糖。幸运的是，有一种方法可以改进它。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("*")），也可以接受一个列表作为第二个参数，以指定要加载的记录。
Shell 中还有其他一些用于处理记录的函数：rd(Name, Definition) 允许你以类似于模块中使用 -record(Name, Definition) 的方式定义记录。你可以使用 rf() 来“卸载”所有记录，或者使用 rf(Name) 或 rf([Names]) 来删除特定定义。
你可以使用 rl() 以一种可以复制粘贴到模块中的方式打印所有记录定义，或者使用 rl(Name) 或 rl([Names]) 来限制它打印特定的记录。
最后，rp(Term) 允许你将元组转换为记录（如果存在定义）。
仅仅写记录不会有太多作用。我们需要一种方法来从记录中提取值。基本上有两种方法可以做到这一点。第一种方法是使用特殊的“点语法”。假设你已经加载了机器人的记录定义
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"]
嗯，语法不太美观。这是因为记录本质上是元组。由于它们只是某种编译器的技巧，你必须保留关键字来定义哪个记录对应哪个变量，因此在 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，并且效果相同。
为了进一步展示记录对元组的依赖关系，请看以下代码
9> #robot.type. 3
这将输出它所对应底层元组的元素位置。
记录的一个优点是，可以在函数头中使用它们进行模式匹配，也可以在守卫中使用它们。在文件顶部声明一个新的记录，然后在下面添加函数
-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
这让我们看到了，在编写函数时，不需要匹配元组的所有部分，甚至不需要知道元组有多少个元素：我们只需要匹配年龄或组别，就可以忽略结构的其余部分。如果我们使用普通元组，函数定义可能需要类似 function({record, _, _, ICareAboutThis, _, _}) -> ... 的形式。然后，每当有人决定向元组中添加一个元素时，其他人（可能对此感到愤怒）就需要去更新使用该元组的所有函数。
以下函数说明了如何更新记录（否则它们就没有太大用处了）
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 中键值存储的认识”的人吧，或者类似的人。听起来像是一个不错的头衔。我只需要其中一条绶带。
对于少量数据，基本上可以使用两种数据结构。第一个叫做属性列表。属性列表是任何形式为 [{Key,Value}] 的元组列表。它们是一种奇怪的结构，因为除了这个规则之外没有其他规则。事实上，规则非常宽松，列表中还可以包含布尔值、整数以及你想要的任何东西。不过，我们更关心的是列表中包含键值对的元组。要使用属性列表，可以使用 proplists 模块。它包含一些函数，例如 proplists:delete/2、proplists:get_value/2、proplists:get_all_values/2、proplists:lookup/2 和 proplists:lookup_all/2。
你会注意到，没有添加或更新列表元素的函数。这表明属性列表作为数据结构的定义非常松散。要获得这些功能，必须手动添加你的元素（[NewElement|OldList]），并使用诸如 lists:keyreplace/4 的函数。对于一个小的数据结构使用两个模块，并不是最干净的做法，但由于属性列表定义如此松散，因此它们经常用于处理配置列表和对给定项目的通用描述。属性列表并不完全是完整的数据结构。它们更像是在使用列表和元组来表示某个对象或项目时出现的常见模式；proplists 模块更像是一个针对这种模式的工具箱。
如果你想要一个更完整的键值存储，用于存储少量数据，那么 orddict 模块是你需要的。Orddict（有序字典）是带有形式感的属性列表。每个键只能出现一次，整个列表已排序，以便更快地进行平均查找等等。对于以下CRUD用法包括 orddict:store/3、orddict:find/2（当你不知道键是否在字典中时）、orddict:fetch/2（当你确信键存在或必须存在时）以及 orddict:erase/2。
Orddict 在复杂性和效率之间取得了很好的平衡，最多可容纳约 75 个元素（参见 我的基准测试）。超过这个数量，你应该切换到其他键值存储。
处理大量数据的关键值结构/模块主要有两种：dicts 和 gb_trees。字典的接口与orddicts相同：dict:store/3，dict:find/2，dict:fetch/2，dict:erase/2以及其他所有函数，例如dict:map/2和dict:fold/2（在整个数据结构上工作非常有用！）。因此，当需要时，dicts 是扩展orddicts 的非常好的选择。
另一方面，通用平衡树拥有更多函数，使您能够更加直接地控制结构的使用方式。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 版本开始，该语言支持新的原生键值数据类型，如附录：映射中所述。它们应该是dict的新的事实上的替代品。
数组
但是，如果代码需要仅包含数字键的数据结构呢？为此，可以使用数组。它们允许您使用数值索引访问元素，并在可能忽略未定义的插槽的情况下对整个结构进行折叠。
不要喝太多酷饮
与它们的命令式对应项相反，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”模块包含一些函数，允许您将族转换为有向图以及有向图转换为族。
队列
它们的实现方式与上面图示类似：两个列表（在本例中为栈），可以快速地追加和预置元素。
队列模块基本上在心理上将不同的函数分为 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 更有意义。这样，以后再学习并发 Erlang 时会更容易，也能专注于所有新概念。让我们开始吧！
