C# 和 F# 中的不可变数据结构
5.00/5 (16投票s)
《Real World Functional Programming》一书使用 C# 3.0 和 F# 中的示例解释了这种范式的基本概念。在本文中，我们将重点介绍支撑函数式程序清晰度的不可变性。
 |
|
这是来自 Tomas Petricek 撰写、Manning Publications 出版的 **Real World Functional Programming** 的章节摘录。内容已重新格式化并编辑，以符合标准的 CodeProject 文章格式。
- 下载源文件（F# 和 C# 3.0）- 2kb
- 下载适用于 VS 2008 的 F# CTP 插件（来自 Microsoft Downloads）
在本文中，我们将探讨构成“函数式编程”范式的几个概念之一。您可能已经注意到，函数式编程这个术语最近在许多领域都出现了——C# 3.0 和 LINQ 很大程度上受到了该范式的影响，而许多能够简化并行代码编写的库都依赖于函数式思想。微软最近还宣布，Visual Studio 2010 将内置 F# —— 一门函数式语言。
函数式范式基于与命令式风格不同的原则。您可能已经知道其中一些概念——例如，C# 3.0 中的“匿名函数”使我们能够将函数用作方法的参数。在函数式编程中，能够编写接受其他函数作为参数或返回其他函数作为结果的函数是基本原则之一。
不可变数据结构
在本文中，我们将探讨另一个影响函数式程序编写方式的概念，即“不可变性”。这意味着程序中使用的对象在构造后无法修改。这具有重要的实际意义——这样编写的代码可以更容易地并行化，因为它不会出现竞态条件。不可变性还使代码更易读，因为程序状态的变化在代码中更加明显，我们可以看到哪个操作改变了状态，哪个没有。在本文中，我们将探讨最简单的函数式数据结构——“元组”，并用它来演示如何使用不可变数据类型。我们将从 F# 的示例开始，但也会研究如何在 C# 3.0 中实现和使用相同的类型。我们将在接下来的章节中看到更常见的函数式数据结构。
我在第一章中已经指出，我们可以使用不可变数据类型或对象编写数据处理函数。与其修改对象的内部状态（这在对象是不可变的因此不可能），处理函数只是创建并返回一个新对象。这个新对象的内部状态将被初始化为原始对象的副本，并在我们想要改变状态的地方有一些差异。这听起来有点抽象，但稍后在示例中您就会明白我的意思。
介绍元组类型
F# 中最简单的不可变数据结构是元组类型。元组是一个简单的类型，它将多个（可能）不同类型的值组合在一起。下面的示例展示了如何创建一个包含两个分组值的实例（称为 `tp`）
> let tp = ("Hello world!", 42) val tp : string * int
创建元组值非常容易：我们只需将用括号括起来的逗号分隔的值列表写出来即可。但让我们更详细地看看代码——第一行，我们创建了一个元组并将其赋值给 `tp` 值。这里使用了 F# 语言的类型推断机制，因此您不必显式声明值的类型。F# 编译器推断出元组的第一个元素是字符串类型，第二个是整数类型，因此构造的元组类型应该是“一个包含字符串作为第一个值，整数作为第二个值的元组”。当然，我们不希望丢失任何类型信息，如果仅仅使用一个名为 Tuple 的类型来表示结果，我们就无法知道它包含字符串和整数。
第二行打印了表达式的推断类型。您可以看到，在 F# 中，元组的类型写为 `string * int`。通常，元组类型写为其成员类型用星号分隔。在接下来的几节中，我们将看到如何在 F# 中使用元组，但我也会向您展示如何在 C# 中实现相同的功能。如果您在阅读 F# 代码后不能立即理解所有内容，请不用担心；只需继续 C# 示例，它们应该会使一切都更加清晰。
那么，我们如何在 C# 中实现相同的类型呢？答案是我们可以使用 C# 2.0 的泛型，并实现一个具有两个类型参数的通用 Tuple 类型。F# 类型 `string * int` 的 C# 等效类型将是 `Tuple
在 F# 中使用元组
现在让我们看一些更复杂的 F# 代码，它使用了元组。在下面的列表中，我们使用元组存储城市信息。第一个成员是一个字符串（城市名称），第二个是一个整数，包含居住在那里的人数。我们实现了一个 `printCity` 函数，它输出一条包含城市名称及其人口的消息，最后我们创建并打印两个城市的信息。
// Function that prints information about the city (1) > let printCity cityInfo = printfn "Population of %s is %d." (fst cityInfo) (snd cityInfo);; // Inferred type of the function (2) val printCity : string * int -> unit // Create tuples representing Prague and Seattle (3) > let prague = ("Prague", 1188126) let seattle = ("Seattle", 594210);; // Types of created tuples (4) val prague : string * int val seattle : string * int // Print information about the cities (5) > printCity prague printCity seattle;; Population of Prague is 1188126. Population of Seattle is 594210.
列表显示了 F# 交互式会话，您可以轻松地自己尝试。第一个代码块 **(1)** 声明了一个 `printCity` 函数，它接受城市信息作为参数，并使用标准的 F# `printfn` 函数打印其值。格式字符串指定第一个参数是字符串，第二个是整数。要读取元组的第一个和第二个元素，我们分别使用两个标准的 F# 函数 `fst` 和 `snd`（它们显然是“first”和“second”的缩写）。
下一行 **(2)** 显示了 F# 类型推断出的函数的类型。我们可以看到，该函数接受一个元组作为参数（用星号表示为 `string * int`），并且不返回任何值（用函数箭头符号右侧的 unit 类型表示）。这正是我们想要的。
接下来，我们创建两个元组值 **(3)**，它们存储了关于布拉格和西雅图的人口信息。输入这些行后，F# 交互式 shell 会打印新声明的值的类型 **(4)**，我们可以看到这些值与 `printCity` 函数接受的参数类型相同。这意味着我们可以将这两个值都作为参数传递给我们的打印函数，并获得预期的结果 **(5)**。
元组的类型与函数的参数类型匹配这一点很重要，否则这两种类型将不兼容，我们也无法调用该函数。为了说明这一点，您可以尝试在 F# 交互式控制台中输入以下代码
let newyork = ("New York", 7180000.5) printCity newyork
我不确定纽约怎会有 7180000.5 个居民，但如果真是如此，那么元组 `newyork` 的类型将不再是 `string * int`，而是 `string * float`，因为类型推断会正确地推断出元组的第二个元素是浮点数。如果您尝试一下，您会发现第二行不是有效的 F# 代码，编译器会报告一个错误，说类型不兼容。
在 C# 中使用元组
我承诺过我们将在 C# 中实现与上一个示例完全相同的代码，所以现在是时候兑现这个承诺并写一些 C# 代码了。正如我之前提到的，我们将使用一个具有两个类型参数的通用类型 `Tuple
该类型将有一个构造函数，带有两个类型分别为 `TFirst` 和 `TSecond` 的参数，以便我们可以构造元组值。它还将提供两个属性来访问其成员的值，因此与 F# 中使用 `fst` 和 `snd` 函数访问元素不同，在 C# 中我们将使用 `First` 和 `Second` 属性。我们暂时跳过实现，转而看看如何使用该类型。下一列表中的代码具有与前一个示例相同的功能，但它是用 C# 编写的。
// Method that takes a tuple as an argument (1)
void PrintCity(Tuple<string, int> cityInfo) {
// Print information about city (2)
Console.WriteLine("Population of {0} is {1}.",
cityInfo.First, cityInfo.Second);
}
// Creatae two sample tuples (3)
var prague = new Tuple<string, int>("Prague", 1188000);
var seattle = new Tuple<string, int>("Seattle", 582000);
// Print information about cities (4)
PrintCity(prague);
PrintCity(seattle);
`PrintCity` 方法接受一个字符串和 `int` 类型的元组作为参数；在 C# 中，我们必须显式指定方法参数的类型，因此您可以看到 `cityInfo` 的类型是 `Tuple
声明两个变量（`prague` 和 `seattle`）并使用带有两个参数的构造函数创建一个元组，该元组存储有关城市的信息 **(3)**；然后使用 `PrintCity` 方法打印城市信息 **(4)**。
一旦我们在 C# 中有了 F# 元组类型的等效类型，从 F# 代码到 C# 代码的转换就非常直接了。代码稍微冗长一些，主要是因为我们必须多次显式指定类型，而在 F# 示例中，类型推断机制能够在所有地方推断出类型。然而，我们很快就会看到这一点可以得到一些改进。我们使用了一个新的 C# 3.0 功能 (`var`)，它至少允许我们在声明 `prague` 和 `seattle` 变量时使用类型推断 **(3)**，因为我们正在初始化变量，并且 C# 可以从赋值的右侧自动推断出类型。
就像在 F# 代码中一样，如果我们声明了一个类型不兼容的元组（例如 `Tuple
在 C# 中实现 Tuple 类型
在 C# 中实现元组类型的过程非常直接。如前所述，我们使用了泛型，因此一个人可以创建一个包含任何两种类型值的元组。
public sealed class Tuple<TFirst, TSecond> {
// Fields are explicitly marked as immutable (1)
private readonly TFirst first;
private readonly TSecond second;
public TFirst First { get { return first; } }
public TSecond Second { get { return second; } }
public Tuple(TFirst first, TSecond second) {
// Initialize fields (2)
this.first = first;
this.second = second;
}
}
最值得注意的可能是该类型是不可变的。我们在第一章中已经看到如何在 C# 中创建不可变类。简而言之，我们使用 `readonly` 修饰符 **(1)** 标记类型的所有字段，并只为两个属性提供 getter。有趣的是，这在某种程度上与 F# 相反，在 F# 中您必须显式标记值为可变的。只读字段只能从构造函数的代码 **(2)** 设置，这意味着一旦对象被创建，它的内部状态就不能被修改，前提是元组中存储的两个值本身也是不可变的。
C# 元组更好的类型推断
在继续之前，我想向您展示一个 C# 技巧，它可以使我们后续使用元组的示例更加简洁。在之前的示例中，我们必须使用构造函数调用来创建我们元组类型的实例，这需要显式指定类型参数。我们使用了新的 C# 3.0 `var` 关键字，以便 C# 编译器为我们推断变量类型，但我们可以做得更好。
C# 在调用泛型方法时还支持类型推断。如果您正在调用一个泛型方法，并且其类型参数用作方法参数的类型，那么编译器可以在调用方法时使用方法参数的编译时类型来推断类型参数。为了说明这一点，让我们看看展示此功能的代码。
public static class Tuple {
public static Tuple<TFirst, TSecond>
Create<TFirst, TSecond>(TFirst first, TSecond second) {
return new Tuple<TFirst, TSecond>(first, second);
}
}
// Create tuples using 'Create' method (1)
var prague = Tuple.Create("Prague", 1188000);
var seattle = Tuple.Create("Seattle", 582000);
代码展示了一个静态方法 `Create` 的实现，该方法有两个通用参数，并创建一个具有这些类型值的元组。我们需要将此方法放在一个非泛型类中，否则我们将不得不显式指定通用参数。幸运的是，C# 允许我们使用 `Tuple` 这个名称，因为类型可以通过其类型参数的数量进行重载（因此 `Tuple` 和 `Tuple
方法的正文非常简单，其唯一目的是使我们能够通过调用方法而不是构造函数来创建元组。这允许 C# 编译器使用 **(1)** 中所示的类型推断。调用泛型方法的完整语法包括类型参数，因此使用完整语法，我们必须编写 `Tuple.Create
计算元组
到目前为止的示例中，我们只是创建了几个元组并打印了值，所以现在让我们执行一些计算。例如，我们可能希望通过添加去年新生的人数来增加居民人数。
正如已经讨论过的，元组类型是不可变的，所以我们不能设置 C# 元组类的属性。在 F# 中，我们可以使用两个函数（`fst` 和 `snd`）读取值，但没有设置值的函数，所以情况类似。这意味着我们的计算必须返回一个新元组，该元组由从初始元组复制的原始城市名称和增加的人口数量组成。
让我们先看看如何在 C# 中做到这一点。下面的源代码片段展示了一个我们将添加到通用 `Tuple
class Tuple<TFirst, TSecond> {
// Returns tuple with the second value changed (1)
public Tuple<TFirst, TSecond> WithSecond(TSecond nsnd) {
return Tuple.Create(this.first, nsnd);
}
}
// Create city information about Prague
var prague0 = Tuple.Create("Prague", 1188000);
// Create information with incremented population
var prague1 = prague0.WithSecond(prague0.Second + 13195);
// Print the new intormation
PrintCity(prague1);
`WithSecond` 方法 **(1)** 接受第二个元素的で值作为参数，并使用 `Tuple.Create` 方法创建一个新的元组，其中第一个元素从当前元组（`this.first`）复制，第二个元素设置为新值 `nsnd`。
现在我们想在 F# 中做同样的事情。在这里，我们将编写一个 `withSecond` 函数，它将执行与我们之前 C# 示例中的 `WithSecond` 方法相同的功能。它将接受一个元组和一个第二个元素的新值，并返回一个新元组，该元组的第一个元素从原始元组复制，第二个元素设置为给定值。
let withSecond tuple nsnd = // Decompose a tuple into two values: 'f' and 's' (1) let (f, s) = tuple // Create a new tuple to return (2) (f, nsnd) // Increment population and print the new information let prague0 = ("Prague", 1188000) let prague1 = withSecond prague0 ((snd prague0) + 13195) printCity prague1
代码首先展示了 `withSecond` 函数的实现。我们可以简单地使用 `fst` 函数来实现它，它读取元组第一个元素的值，但我希望演示另一个可以与元组一起使用的 F# 功能：模式匹配。您可以看到，在函数内部，我们首先将给定的元组分解为两个单独的值 **(1)**，并将这两个值命名为 `f` 和 `s`（分别代表 first 和 second）。这就是模式匹配发生的地方；在等号的左侧，您可以看到一个称为模式的语言结构，在右侧，我们有一个与模式匹配的表达式。模式匹配获取表达式的值并将其分解为模式内部使用的值。
在下一行 **(2)** 中，我们可以使用通过模式匹配从元组中提取的值 `f`。我们使用原始第一个元素的值和作为参数给出的第二个元素的新值（`nsnd`）来重建元组。我们将在下一节中查看更多关于元组模式匹配的示例。除了使用模式匹配，代码没有显示任何新内容，但模式匹配是一个重要主题，F# 也提供了其他使用它的方法。让我们仔细看看。
元组模式匹配
在上一个示例中，我们在 let 绑定中分解了元组。我们可以稍微改进前面的代码示例。由于我们实际上没有使用元组的第二个元素，我们只需要给第一个元素指定一个名称。为此，我们可以为模式中的第二个值写一个下划线，如下所示：
let (f, _) = tuple
下划线是一个特殊模式，它匹配任何表达式并忽略赋给它的值。在 let 绑定中使用模式匹配通常非常有用，但您也可以在其他地方使用它。事实上，模式几乎可以出现在任何将表达式赋给某个值的场合。例如，另一个模式匹配极其有用的地方是当我们指定函数的参数时。我们可以使用模式来代替参数名。这使我们的 `setSecond` 函数更加简单。
let withSecond (f, _) nsnd = (f, nsnd)
现在我们已经将声明从三行缩短到一行。结果不使用任何不必要的值，并清楚地显示了数据如何在代码中流动。仅从代码本身可以看出，原始元组的第一个元素被复制（通过跟踪符号 `f` 的使用），并且第二个函数参数被用作返回元组的第二个元素（通过跟踪 `nsnd` 的使用）。这是我们在将要编写的大多数 F# 函数中使用元组的首选方式。
模式匹配的另一个常见用途是在 F# 的 `match` 表达式中，我们之前已经见过。我们可以像这样重写我们的 `withSecond` 函数以使用 `match` 表达式：
let withSecond tuple nsnd =
match tuple with
| (f, _) -> (f, nsnd)
match 结构允许我们将指定的表达式（`tuple`）与一个或多个模式进行匹配，这些模式以竖线符号开头。在我们的示例中，我们只有一个模式，并且因为任何具有两个元素的元组都可以分解为包含其元素的两个值，所以执行将始终遵循这一个分支。F# 编译器分析模式匹配以推断参数元组是一个包含两个元素的元组类型。
注意
请记住，您不能使用模式匹配来确定元组有两或三个元素。这将导致编译时错误，因为模式必须与我们正在匹配的表达式具有相同的类型，而一个有三个元素的元组类型（例如 `int * int * int`）与一个有两个元素的元组类型（例如 `int * int`）不兼容。模式匹配只能用于确定值的运行时属性；元组中的元素数量由元组类型指定，该类型在编译时进行检查。如果您想知道如何表示可能具有几个不同值的某些数据类型，那么您需要等到第 5 章，届时我们将研究联合。
在前面的示例中，我们使用了不会失败的模式，因为所有两个元素的元组都可以分解为单独的元素。这在 F# 中称为完整模式。当处理不完整且可能失败的模式时，`match` 结构特别有用，因为我们可以指定多个不同的模式（每个模式在新的一行上，以竖线符号开头），如果第一个模式失败，则尝试下一个模式，直到找到一个成功的模式。
对于元组来说，什么是不完整的模式呢？嗯，我们可以写一个模式，该模式仅在第一个元素（城市名称）是某个特定值时才匹配。例如，假设纽约有 100 人从未被任何统计研究统计过，因此在设置元组的第二个元素（城市人口）时，我们希望在城市是纽约时添加 100。当然，您可以使用 `if` 表达式来完成此操作，但以下示例展示了一种使用模式匹配的更优雅的解决方案。
> let setSecond tuple nsnd = match tuple with // Pattern that matches only New York (1) | ("New York", _) -> ("New York", nsnd + 100) // Pattern that matches all other values (2) | (f, _) -> (f, nsnd) ;; val setSecond : string * 'a -> int -> string * int > let prague = ("Prague", 123) setSecond prague 10;; // The expected result for Prague val it : string * int = ("Prague", 10) > let ny = ("New York", 123) setSecond ny 10;; // Returned population is incremented by 100 val it : string * int = ("New York", 110)
您可以看到，在此示例中，match 表达式包含两个不同的模式。第一个模式包含一个字符串“New York”作为第一个元素，下划线作为第二个元素 **(1)**。这意味着它仅匹配第一个元素设置为“New York”且第二个元素具有任何值的元组。当匹配此模式时，我们将返回一个代表纽约的元组，但人口比给定的参数多 100。第二个模式 **(2)** 与之前的示例相同，它只是设置了元组的第二个元素。
函数声明之后的示例显示了代码的行为符合预期。如果我们尝试设置新的人口普查数据（例如，布拉格的新人口），则会使用新的人口值，但如果我们尝试为纽约这样做，则新的人口值将增加一百。
元组在开发初期特别频繁地使用，因为它们非常简单。在下一节中，我们将研究另一种基本的不可变数据类型：列表。我们已经看到，元组代表具有不同类型的已知数量的元素。列表的工作方式则相反：列表代表相同类型的未知数量的元素。
摘要
在本文中，我们探讨了许多函数式语言中都存在的一种类型——元组。我们已经看到了如何在 F# 中使用元组，然后在 C# 中实现了相同的类型（作为一个通用类 `Tuple