头等函数

map :: (a -> b) ->  -> map f      = map f (x:xs) = f x : map f xs

void map(int (*f)(int), int x, size_t n) {    for (int i = 0; i < n; i++)        x = f(x);}

main = map (\x -> 3 * x + 1) 

int f(int x) {    return 3 * x + 1;}int main() {    int list = {1, 2, 3, 4, 5};    map(f, list, 5);}

非局部变量与闭包

一旦有了匿名函数与嵌套函数，引用函数体之外的变量（非局部变量）就很自然了：

main = let a = 3           b = 1        in map (\x -> a * x + b) 

如果函数只能用函数指针表示，如何把函数体之外的值传递给函数就是个问题。可以手工建立一个闭包，但显然这不能算作头等函数：

typedef struct {    int (*f)(int, int, int);    int *a;    int *b;} closure_t;void map(closure_t *closure, int x, size_t n) {    for (int i = 0; i < n; ++i)        x = (*closure->f)(*closure->a, *closure->b, x);}int f(int a, int b, int x) {    return a * x + b;}void main() {    int l = {1, 2, 3, 4, 5};    int a = 3;    int b = 1;    closure_t closure = {f, &a, &b};    map(&closure, l, 5);}

注意这里的map是特化为使用当前环境外的两个int。即使f是个嵌套函数，仍然要面对同样问题，这也是C语言不支持嵌套函数的理由。

返回结果为函数时，实际上返回的是该函数的闭包。对于C语言，函数退出时其局部变量也退出了各自的作用域，这使得构建闭包变得困难。这被称为向上的函数参数问题（英语：upwards funarg problem）。

把函数赋值给变量面临着把函数当作返回结果一样的困难：构建该函数的闭包：

f ::  -> ]f = let a = 3        b = 1     in 

函数的相等

判断两个函数是否相等，有不同的判据：

对于类型论，函数类型接受值类型并返回值类型可写为 → 或。根据柯里-霍华德对应，函数类型可对应于逻辑蕴涵，lambda抽象对应于discharging hypothetical assumptions，函数调用对应于肯定前件推理规则。类型论还使用头等函数建模关联数组与类似的数据结构。

对于范畴论，头等函数对应于closed category（英语：closed category）设置。例如，简单类型λ演算 对应于笛卡儿闭范畴(CCC)的内部语言。

函数式程序设计语言，如Scheme、ML、Haskell、F#、Scala，都具有完整的头等函数。Lisp作为最早的函数式语言在当初设计时对头等函数各方面还没有适当的理解，导致了采用动态作用域。后来的Common Lisp已经改为使用词法作用域的头等函数。

许多脚本语言，如Perl、Python、PHP、Lua、Tcl/Tk、JavaScript、Io，有头等函数。

指令式程序设计语言，Algol及Pascal族系、C族系，与现代有垃圾收集的语言非常不同。Algol族系允许嵌套函数与高阶函数作为参数，但不允许函数作为返回值（除了Algol 68）。因为当时还不清楚如何处理内嵌函数作为返回值时的非局部变量问题（Algol 68对此会产生运行期错误）。

C族系允许函数作为参数与函数作为返回值，但由于不支持嵌套函数而避开了相关问题。因为返回嵌套函数并捕获所使用的非局部变量被认为才是真正有用，因此C族系不被认为有头等函数。

现代指令式编程语言由于有垃圾收集功能而使得头等函数成为可能。很多语言的后续版本开始支持头等函数，如C# 2.0，Apple公司的C、C++与Objective-C的Block扩展。C++11开始支持了匿名函数与闭包。