1.3 高階函數
目前為止，我們看過由整數到整數的函數、由整數到真假值的函數... 那麼，可以有由函數到函數的函數嗎？ 函數語言將函數視為重要的構成元件，因此函數也被視為一級公民。 如果整數、真假值... 可以當作參數、可以被函數傳回，函數當然也可以。 一個「輸入或輸出也是函數」的函數被稱為高階函數(higher order function)。 Haskell 甚至設計了許多鼓勵我們使用高階函數的機制。 本書中我們將見到許多高階函數。其實，我們已經看過一個例子了。
一級公民
在程式語言中，若說某物/某概念是一級公民(first-class citizen)或「一級的」， 通常指它和其他事物被同等對待： 如果其他事物可被當作參數、可被當作傳回值、可被覆寫...那麼它也可以。 這是一個沒有嚴格形式定義的說法，由 Christopher Strachey 在 1960 年代提出， 可用在型別、值、物件、模組... 等等之上。
例如：OCaml 是個有「一級模組」的語言，因為 OCaml 模組也可當作參數，可定義從模組到模組的函數（OCaml 中稱之為 functor）。 在 C 語言之中函數是次級的，因為函數不能當參數傳（能傳的是函數的指標，而非函數本身）。 Strachey指出，在 Algol 中實數是一級的，而程序是次級的。
Currying 回顧smaller的定義：
smaller :: Int -> Int -> Int
smaller x y = if x <= y then x else y
1.2 節中說「smaller 是一個函數，拿兩個參數 x 與 y」。
但這僅是口語上方便的說法。
事實上，在 Haskell 中（如同在 $\lambda$-calculus 中），所有函數都只有一個參數。
函數 smaller 其實是一個\emph{傳回函數的函數}：
smaller的型別Int -> Int -> Int其實應看成Int -> (Int -> Int)： 這個函數拿到一個Int後，會傳回一個型別為Int -> Int的函數。smaller 3的型別是Int -> Int。這個函數還可拿一個Int參數，將之和3比大小，傳回較小的那個。smaller 3 4是一個Int。它其實是將函數smaller 3作用在4之上。也就是說，smaller 3 4其實應看成(smaller 3) 4. 根據定義，它可展開為if 3 <= 4 then 3 else 4，然後化簡為3.
練習 1.4
將 smaller 的定義鍵入一個檔案，載入 Haskell 直譯器中。
smaller 3 4的型別是什麼？在 GHCi 中可用 {\tt :t e} 指令得到算式e的型別。smaller 3的型別是什麼？在檔案中定義
st3 = smaller 3. 函數st3的型別是什麼？給
st3一些參數，觀察其行為。
「用『傳回函數的函數』模擬『接收多個參數的函數』」這種做法稱作 currying.
Currying 為動名詞，形容詞則為 curried。
此詞來自於邏輯學家 Haskell B. Curry 的姓氏。
詳見第 1.11 節。
Haskell 鼓勵大家使用 currying --- 它的內建函數大多依此配合設計，
語法設計上也很給 currying 方便。
當型別中出現連續的 (->) 時，預設為往右邊結合，例如
Int -> Int -> Int 應看成 Int -> (Int -> Int).
這使得「傳回函數的函數」容易寫。
而在值的層次，連續的函數應用往左結合。
例如，(smaller 3) 4 可寫成 smaller 3 4。
這讓我們能很方便地將參數一個個餵給 curried 函數。
另一方面，如果我們想使用 double 兩次，計算 x 的四倍，應寫成 double (double x).
若寫 double double x ，會被視為 (double double) x --- double 作用在自身之上，而這顯然是個型別錯誤。
我們再看一個使用 currying 的練習：
例 1.4
給定 a, b, c, x, 下述函數 poly 計算 $ax^2 + bx + c$:
poly :: Int -> Int -> Int -> Int -> Int
poly a b c x = a * x * x + b * x + c
請定義一個函數 poly1, 使得 $poly_1~x = x^2 + 2x + 1$.
函數 poly1 需使用 poly.
答案
一種作法是：
poly1 :: Int -> Int
poly1 x = poly 1 2 1 x
但這相當於 poly1 x = (poly 1 2 1) x ---
poly 拿到 x 後，立刻把 x 傳給 poly 1 2 1 這個函數。
因此 poly1 可更精簡地寫成：
poly1 :: Int -> Int
poly1 = poly 1 2 1
兩種寫法都有人使用。
有提及x的寫法著重於描述拿到參數x之後要對它進行什麼操作。
而省略x的寫法則是在函數的層次上思考：
我們要定義一個函數，稱作poly1。這個函數是什麼呢？
就是 poly 拿到 1, 2, 1 之後傳回的那個函數。
如果我們想用 poly 定義出另一個函數
$poly_2~a~b~c = a\times 2^2 + b \times 2 + 2$ 呢？
最好理解的可能是不怎麼意外的寫法：
poly :: Int -> Int -> Int -> Int
poly2 a b c = poly a b c 2
我們可以用一些技巧使 a, b, 和c不出現在定義中，
但如此得到的程式並不會更好懂。
二元運算子
在進入其他主題前，我們交代一些語法細節。
Haskell 鼓勵 currying 的使用，也把二元運算子都設計成 curried 的。
例如加法的型別是 Int -> Int -> Int.
Haskell 也配套設計了種種關於二元運算子的特殊語法，希望讓它們更好用。
但這些語法規則的存在都僅是為了方便我們寫出（主觀上）語法漂亮的程式，
而不是非有不可、非學不可的規定。
假設某二元運算子 oplus 的型別是 a -> b -> c,
(x ⊕) 是給定了 oplus 的第一個參數後得到的函數；
(⊕ y) 則是給定了 oplus 的第二個參數後得到的函數：
根據Hudak et al. [2007]，此種「切片」(sectioning)語法最早見於 David Wile 的博士論文。
後來被包括 Richard Bird 在內的 IFIP WG 2.1 成員使用，並由 David A. Turner 實作在他的語言 Miranda 中。
(x ⊕) y = x ⊕ y {-"\quad"-} {- (x ⊕) 的型別為 b -> c; -}
(⊕ y) x = x ⊕ y {- (⊕ y) 的型別為 a -> c.-}
例如：
(2 *)和(* 2)都是把一個數字乘以二的函數；(/ 2)則把輸入數字除以二；(1 /)計算輸入數字的倒數。
名字以英文字母開頭的函數預設為前序的。例如，
計算餘數的函數 mod 使用時得寫成 mod 6 4。
若把它放在「倒引號(backquote)」中，表示將其轉為中序 ---
如果我們比較喜歡把 mod 放到中間，可以寫成 6 `mod` 4.
首字元非英文字母的函數（如 (+), (/) 等）則會被預設為中序的二元運算子。
若把一個中序二元運算子放在括號中，表示將其轉為前序運算子。
例如，(+) 1 2 和 1 + 2 的意思相同。
在 Haskell 的設計中，函數應用的優先順序比中序運算子高。
因此 double 3 + 4 會被視作 (double 3) + 4, 而不是 double (3+4).
將中序運算子放在括號中也有「讓它不再是個中序運算子，只是個一般識別字」的意思。
例如算式 f + x 中，f 和 x 是中序運算子 (+) 的參數。
但在 f (+) x 中，(+) 和 x 都是 f 的參數
（這個式子可以讀解為 (f (+)) x）。
以函數為參數 下述函數 square 計算輸入的平方：
square :: Int -> Int
square x = x * x
我們可另定義一個函數 quad :: Int -> Int，把 square 用兩次，
使得 quad x 算出 $x^4$.
quad :: Int -> Int
quad x = square (square x)
但，「把某函數用兩次」是個常見的編程模式。
我們能不能把 quad 與 square 抽象掉，單獨談「用兩次」這件事呢？
下面的函數 twice 把參數 f 在 x 之上用兩次：
twice :: (a -> a) -> (a -> a)
twice f x = f (f x)
有了 twice, 我們可以這麼定義 quad:
quad :: Int -> Int
quad = twice square
函數 twice 是本書中第一個「以函數為參數」的函數。
我們可看到「讓函數可作為參數」對於抽象化是有益的：
我們可以把「做兩次」這件事單獨拿出來說，把「做什麼」抽象掉。
「函數可以當作參數」意味著我們可以定義作用在函數上的運算子。
twice 就是這麼一個運算子：
它拿一個函數 f，把它加工一下，做出另一個函數（後者的定義是把 f 用兩次）。
參數式多型
函數 twice 也是本書中第一個多型函數。
在 Haskell 的型別中，小寫開頭的識別字（如其中的 a）是型別層次的參數。
讀者可想像成在 twice 的型別最外層有一個省略掉的 ∀ a.
也就是說, twice 的完整型別是 ∀ a . (a -> a) -> (a -> a) ---
對所有的型別 a, twice 都可拿一個型別為 a -> a 的函數，
然後傳回一個型別為 a -> a 的函數。
在 twice 的型別 (a -> a) -> (a -> a) 中，
第一個
a -> a是參數f的型別，在第二個
a -> a中，第一個a是 參數x的型別，第二個
a則是整個計算結果的型別。
參數 f 的型別必須是 a -> a: 輸出入型別必須一樣，因為 f 的結果必須可當作 f 自己的輸入。
在 twice 被使用時，型別參數 a 會依照上下文被特化(instantiate)成別的型別。
例如 twice square 中， 因為 square 的型別是 Int -> Int,
這一個 twice 的型別變成了 (Int -> Int) -> (Int -> Int) --- a 被特化成 Int.
若某函數 k 的型別是 Float -> Float, 在 twice k 中，twice 的型別是 (Float -> Float) -> (Float -> Float)。
同一個函數 twice 可能依其上下文而有許多不同的型別，但都是 (a -> a) -> (a -> a) 的特例。
「一段程式可能有許多不同型別」的現象稱作多型(polymorphism)。
多型又有許多種類，此處為其中一種。詳情見... \todo{}
練習 1.5
為何 twice 的型別不可以是 (a -> b) -> (a -> b)?
例 1.5
forktimes f g x = f x * g x
算式 forktimes f g x 把 f x 和 g x 的結果乘起來。
請想想
forktimes的型別該是什麼？試定義函數
compute :: Int -> Int, 使用forktimes計算 $x^2 + 3\times x + 2$。 提示：$x^2 + 3\times x + 2 = (x+1) \times (x+2)$.
答案
如同 twice, forktimes 可以有很多型別，但都應該是
(a -> Int) -> (a -> Int) -> a -> Int 的特例：
在 forktimes f g x 中， f 和 g 的型別可以是 a -> Int,
其中 a 可以是任何型別 a，而 x 的型別必須也是同一個 a.
函數 compute 可定義如下：
compute :: Int -> Int
compute = forktimes (+1) (+2)
其中 forktimes 型別中的 a 被特化為 Int.
如前所述，forktimes f g x 把 f x 和 g x 的結果乘起來。
但，一定得是乘法嗎？我們當然可以再多做一點點抽象化。
例 1.6
考慮函數 lift2 h f g x = h (f x) (g x).
lift2的型別是什麼？用
lift2定義forktimes.用
lift2計算 $x^2 + 3\times x + 2$.
答案
我們把 lift2 最泛用的型別和其定義重複如下：
lift2 :: (a -> b -> c) -> (d -> a) -> (d -> b) -> d -> c
lift2 h f g x = h (f x) (g x)
有了 lift2, forktimes 可定義為：
forktimes :: (a -> Int) -> (a -> Int) -> a -> Int
forktimes = lift2 (*)
請讀者觀察：lift 型別中的 a, b, c 都特化成 Int,
d 則改名為 a.
我們也可用 lift2 定義 compute:
compute :: Int -> Int
compute = lift2 (*) (+1) (+2)
函數 lift2 可以看作一個作用在二元運算子上的運算子，功用是把
二元運算子「提升」到函數層次。
例如，原本 (*) 只能拿兩個 Int 當作參數，
（例：1 * 2 是「把 1 和 2 乘起來」），
但現在 lift2 (*) 可將函數 (+1) 和 (+2) 當參數了，
意思為「把 (+1) 和 (+2) 的結果乘起來」。