頭等函式（first-class function）是指在程式設計語言中，函式被當作頭等公民。這意味著，函式可以作為別的函式的參數、函式的返回值，賦值給變數或存儲在數據結構中。 有人主張應包括支持匿名函式（函式字面量，function literals）。在這樣的語言中，函式的名字沒有特殊含義，它們被當作具有函式類型的普通的變數對待。1960年代中期，克里斯托弗·斯特雷奇在“functions as first-class citizens”中提出這一概念。
基本介紹
- 中文名：頭等函式
- 外文名：first-class function
- 學科：程式語言術語
簡介,概念,高階函式：函式作為實參傳遞,高階函式：返回函式作為結果,函式賦值給變數,類型論,
簡介
頭等函式是函式式程式設計所必須的。通常要使用高階函式。map函式就是一個高階函式，其實參是一個函式及一個list，返回結果是把作為參數的函式作用於list的每個元素後的結果形成的list。
把函式作為函式參數與函式返回值會遇到特別的困難。特別是存在非局部變數與嵌套函式、匿名函式。歷史上，這被稱作函式參數問題。早期的命令式程式語言，或者不支持函式作為結果類型（如ALGOL 60,Pascal），或者忽略嵌套函式與非局部變數（如C語言）。早期的函式式語言Lisp採取了動態作用域方法，把非局部變數綁定到函式執行點最近的變數定義。Scheme語言支持詞法作用域的頭等函式，把對函式的引用綁定到閉包（closure）而不是函式指針，這使得垃圾收集成為必須。
概念
在這一節，比較把函式視作頭等公民的典型的函式式語言Haskell與把函式視作二等公民的命令式編程的C語言的有關概念。
高階函式：函式作為實參傳遞
更多信息：高階函式
具有函式參數的函式，稱為高階函式。函式式語言如Haskell：
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs
函式不是頭等公民的程式設計語言可以使用函式指針或delegate，實現函式作為參數。C語言例子：
void map(int (*f)(int), int x[], size_t n) { for (int i = 0; i < n; i++) x[i] = f(x[i]);}
高階函式：返回函式作為結果
返回結果為函式時，實際上返回的是該函式的閉包。對於C語言，函式退出時其局部變數也退出了各自的作用域，這使得構建閉包變得困難。這被稱為向上的函式參數問題。
函式賦值給變數
把函式賦值給變數面臨著把函式當作返回結果一樣的困難：構建該函式的閉包：
f :: [[Integer] -> [Integer]]f = let a = 3 b = 1 in [map (\x -> a * x + b), map (\x -> b * x + a)]
類型論
主條目：函式類型
對於類型論，函式類型接受值類型A並返回值類型B可寫為A→B或B。根據柯里-霍華德對應，函式類型可對應於邏輯蘊涵，lambda抽象對應於
，函式調用對應於肯定前件推理規則。類型論還使用頭等函式建模關聯數組與類似的數據結構。
對於範疇論，頭等函式對應於closed category設定。例如，簡單類型λ演算對應於笛卡兒閉範疇(CCC)的內部語言。
