头等函数

在计算机科学中，如果一种编程语言将函数视为一等公民，则称该语言具有一等函数。 这意味着该语言支持将函数作为参数传递给其他函数，将它们作为其他函数的值返回，并将它们分配给变量或将它们存储在数据结构中。 一些编程语言理论家也需要支持匿名函数（函数文字）。 在具有一等函数的语言中，函数的名称没有任何特殊地位； 它们被视为具有函数类型的普通变量。 这个词是克里斯托弗·斯特拉奇 (Christopher Strachey) 在 20 世纪 60 年代中期在作为一等公民的职能背景下创造的。

头等函数是函数式编程风格的必要条件，在这种风格中，使用高阶函数是一种标准做法。 高阶函数的一个简单示例是 map 函数，它以函数和列表作为参数，并返回通过将函数应用于列表的每个成员而形成的列表。 对于支持映射的语言，它必须支持将函数作为参数传递。

将函数作为参数传递或将它们作为结果返回存在一定的实现困难，尤其是在嵌套函数和匿名函数中引入非局部变量的情况下。 从历史上看，这些被称为 funarg 问题，这个名字来自函数参数。 在早期的命令式语言中，这些问题通过不支持函数作为结果类型（例如 ALGOL 60、Pascal）或省略嵌套函数和非局部变量（例如 C）来避免。 早期的函数式语言 Lisp 采用了动态作用域的方法，其中非局部变量指的是该变量在函数执行点的最接近定义，而不是定义它的位置。 在 Scheme 中引入了对词法作用域的一等函数的适当支持，并且需要将对函数的引用作为闭包而不是裸函数指针来处理，这反过来使得垃圾收集成为必要。

在本节中，我们比较了如何在具有一等函数的函数式语言 (Haskell) 和函数是二等公民 (C) 的命令式语言中处理特定的编程习语。

在函数是一等公民的语言中，函数可以像其他值一样作为参数传递给其他函数（将另一个函数作为参数的函数称为高阶函数）。 在 Haskell 语言中：

映射::(a -> b) -> [a]-> [b]地图 f [] = []地图 f (x:xs) = f x : 地图 f xs

函数不是一流的语言通常仍然允许通过使用函数指针或委托等特性来编写高阶函数。

这两种方法之间存在许多差异，这些差异与对一等函数的支持没有直接关系。 Haskell 示例对列表进行操作，而 C 示例对数组进行操作。 两者都是各自语言中最自然的复合数据结构，让 C 示例对链表进行操作会使它变得不必要的复杂。 这也解释了 C 函数需要一个附加参数（给出数组的大小）这一事实。C 函数就地更新数组，不返回任何值，而在 Haskell 中数据结构是持久的（返回一个新列表 而旧的保持不变。）Haskell 示例使用递归遍历列表，而 C 示例使用迭代。 同样，这是用两种语言表达这个函数的最自然的方式，但是 Haskell 示例可以很容易地用折叠来表达，而 C 示例可以用递归来表达。 最后，Haskell 函数有一个多态类型，因为 C 不支持它，我们将所有类型变量固定为类型常量 int。

在支持匿名函数的语言中，我们可以将这样的函数作为参数传递给高阶函数

在不支持匿名函数的语言中，我们必须将其绑定到一个名称

一旦我们有了匿名或嵌套函数，它们就很自然地引用它们主体之外的变量（称为非局部变量）

如果函数用裸函数指针表示，我们就无法再知道函数体之外的值应该如何传递给它，因此需要手动构建闭包。