Haskell/高階函式
函數語言程式設計的核心思想是函式就像任何其他值一樣。函式式風格的力量來自將函式本身作為普通值處理，即透過將函式傳遞給其他函式以及從函式返回函式。接受另一個函式（或多個函式）作為引數的函式稱為高階函式。它們幾乎可以在任何 Haskell 程式中找到，實際上我們已經遇到了一些，例如map和各種 folds。在討論列表 II中的map時，我們看到了高階函式的常見示例。現在，我們將探索一些操作函式的常見程式碼編寫方法。
為了有一個具體的例子，我們將考慮對列表進行排序的任務。快速排序是一種眾所周知的遞迴排序演算法。要將它的排序策略應用於列表，我們首先選擇一個元素，然後將列表的其餘部分分成 (A) 應該放在所選元素之前的元素，(B) 等於所選元素的元素，以及 (C) 應該放在之後的元素。然後，我們將相同的演算法應用於未排序的 (A) 和 (C) 列表。經過足夠的遞迴排序後，我們將所有內容拼接在一起，得到最終的排序列表。這種策略可以非常簡單地轉換為 Haskell 實現。
-- Type signature: any list with elements in the Ord class can be sorted.
quickSort :: (Ord a) => [a] -> [a]
-- Base case:
-- If the list is empty, there is nothing to do.
quickSort [] = []
-- The recursive case:
-- We pick the first element as our "pivot", the rest is to be sorted.
-- Note how the pivot itself ends up included in the middle part.
quickSort (x : xs) = (quickSort less) ++ (x : equal) ++ (quickSort more)
where
less = filter (< x) xs
equal = filter (== x) xs
more = filter (> x) xs
應該指出的是，我們的quickSort相當天真。更有效的實現將避免在每個遞迴步驟中對filter進行三次遍歷，並且不會使用(++)來構建排序列表。此外，與我們的實現不同，原始快速排序演算法使用可變性在記憶體中進行排序。[1] 我們現在將忽略這些問題，因為我們更感興趣的是排序函式的使用模式，而不是準確的實現。
Haskell 中幾乎所有基本資料型別都是Ord類的成員，Ord類用於排序測試，就像Eq類用於相等性測試一樣。Ord類定義了給定型別的“自然”排序。它提供了一個名為compare的函式，其型別為
compare :: (Ord a) => a -> a -> Ordering
compare接受兩個值並比較它們，返回一個Ordering值，如果第一個值小於第二個值，則為LT；如果相等，則為EQ；如果大於，則為GT。對於Ord型別，(<)、來自Eq的(==)和(>)可以看作是compare的快捷方式，它們檢查三種可能性之一，並返回一個Bool來指示指定的排序是否根據該型別的Ord規範為真。請注意，我們在quickSort定義中使用filter的每個測試都對應於compare的可能結果之一，因此我們可能寫過，例如，less為less = filter (\y -> y `compare` x == LT) xs。
使用quickSort，對任何元素位於Ord類中的列表進行排序都很容易。假設我們有一個String列表，我們想要對它們進行排序；我們只需將quickSort應用於該列表。在本章的其餘部分，我們將使用一個只有幾個詞的偽詞典（但包含數千個詞的詞典也能同樣有效）。
dictionary = ["I", "have", "a", "thing", "for", "Linux"]
quickSort dictionary返回
["I", "Linux", "a", "for", "have", "thing"]
如您所見，預設情況下會考慮大小寫進行排序。Haskell String是 Unicode 字元的列表。Unicode（以及幾乎所有其他字元編碼）指定大寫字母的字元程式碼小於小寫字母的字元程式碼。因此“Z”小於“a”。
為了獲得正確的類似詞典的排序，我們需要一個不區分大小寫的quickSort。為了實現這一點，我們可以從上面compare的討論中獲得提示。quickSort的遞迴情況可以改寫為
quickSort compare (x : xs) = (quickSort compare less) ++ (x : equal) ++ (quickSort compare more)
where
less = filter (\y -> y `compare` x == LT) xs
equal = filter (\y -> y `compare` x == EQ) xs
more = filter (\y -> y `compare` x == GT) xs
雖然這個版本不如原始版本整潔，但它表明元素的排序完全取決於compare函式。這意味著我們只需要用我們選擇的(Ord a) => a -> a -> Ordering函式替換compare即可。因此，我們更新的quickSort'是一個高階函式，它接受一個比較函式和要排序的列表。
quickSort' :: (Ord a) => (a -> a -> Ordering) -> [a] -> [a]
-- No matter how we compare two things the base case doesn't change,
-- so we use the _ "wildcard" to ignore the comparison function.
quickSort' _ [] = []
-- c is our comparison function
quickSort' c (x : xs) = (quickSort' c less) ++ (x : equal) ++ (quickSort' c more)
where
less = filter (\y -> y `c` x == LT) xs
equal = filter (\y -> y `c` x == EQ) xs
more = filter (\y -> y `c` x == GT) xs
我們可以重複使用我們的quickSort'函式來服務於許多不同的目的。
如果我們想要降序，我們只需使用reverse (quickSort dictionary)反轉我們最初排序的列表。然而，為了真正按降序進行初始排序，我們可以為quickSort'提供一個比較函式，該函式返回通常的Ordering的反面。
-- the usual ordering uses the compare function from the Ord class
usual = compare
-- the descending ordering, note we flip the order of the arguments to compare
descending x y = compare y x
-- the case-insensitive version is left as an exercise!
insensitive = ...
-- How can we do case-insensitive comparisons without making a big list of all possible cases?
注意
Data.List提供了一個用於排序列表的sort函式。它沒有使用快速排序；相反，它使用了對稱為歸併排序的演算法的有效實現。Data.List還包括sortBy，它接受一個自定義比較函式，就像我們的quickSort'一樣。
| 練習 |
|---|
編寫insensitive，使得quickSort' insensitive dictionary給出["a", "for", "have", "I", "Linux", "thing"]。 |
 |
一位讀者要求對本頁面的內容進行澄清，以減少混淆。 您可以幫助澄清材料，請求幫助，或檢視當前進度。 |
柯里化（在走向最終結果的途中生成中間函式）的概念最早在早期的“列表 II”一章中介紹。這是一個回顧柯里化工作原理的好地方。
我們的quickSort'的型別為(a -> a -> Ordering) -> [a] -> [a]。
大多數情況下，高階函式的型別提供了一個使用它的指南。閱讀型別簽名的一種直接方法是“quickSort'首先接受一個函式作為引數，該函式給出兩個a的排序。它的第二個引數是一個a列表。最後，它返回一個新的a列表”。這足以正確地猜測它使用給定的排序函式對列表進行排序。
請注意，圍繞a -> a -> Ordering的括號是必須的。它們指定a -> a -> Ordering構成單個引數，該引數恰好是一個函式。
如果沒有括號，我們將得到a -> a -> Ordering -> [a] -> [a]，它接受四個引數（沒有一個是函式本身），而不是我們想要的兩個，並且它不會按預期工作。
請記住，->運算子是右結合的。因此，我們錯誤的型別簽名a -> a -> Ordering -> [a] -> [a]與a -> (a -> (Ordering -> ([a] -> [a])))含義相同。
鑑於->是右結合的，正確quickSort'簽名的顯式分組版本實際上是(a -> a -> Ordering) -> ([a] -> [a])。這非常合理。我們最初缺少可調整比較函式引數的quickSort的型別為[a] -> [a]。它接受一個列表並對其進行排序。我們新的quickSort'只是一個生成quickSort風格函式的函式！如果我們為(a -> a -> Ordering)部分插入compare，那麼我們只是返回我們最初的簡單quickSort函式。如果我們對引數使用不同的比較函式，我們會生成一個不同的quickSort函式變體。
當然，如果我們不僅給出一個比較函式作為引數，而且還輸入一個實際要排序的列表，那麼最終的結果就不是新的quickSort風格函式；相反，它會繼續並將列表傳遞給新函式，並返回排序後的列表作為我們的最終結果。
| 練習 |
|---|
|
（具有挑戰性） 以下練習結合了您已經瞭解的高階函式、遞迴和 I/O。我們將重新建立在命令式語言中稱為for 迴圈的東西。實現一個函式 for :: a -> (a -> Bool) -> (a -> a) -> (a -> IO ()) -> IO () for i p f job = -- ??? 使用此函式的示例可能是 for 1 (<10) (+1) print 它在螢幕上列印數字 1 到 9。
一些更具挑戰性的練習，你可以嘗試一下
|
我們將透過討論一些常見且有用的通用高階函式的示例來結束本章。熟悉這些將大大提高你在編寫和閱讀 Haskell 程式碼方面的技能。
flip 是一個方便的小型 Prelude 函式。它接受一個具有兩個引數的函式，並返回具有相同函式但引數交換後的版本。
flip :: (a -> b -> c) -> b -> a -> c
flip 在使用中
Prelude> (flip (/)) 3 1 0.3333333333333333 Prelude> (flip map) [1,2,3] (*2) [2,4,6]
我們可以使用 flip 來編寫 quickSort 示例中 descending 比較函式的無點版本
descending = flip compare
當我們想將一個具有兩個不同型別引數的函式傳遞給另一個函式，而這些引數相對於高階函式的簽名處於錯誤順序時，flip 特別有用。
(.) 組合運算子是另一個高階函式。它具有以下簽名
(.) :: (b -> c) -> (a -> b) -> a -> c
(.) 接受兩個函式作為引數，並返回一個新函式，該函式將第二個函式應用於引數，然後是第一個函式。（將 (.) 的型別寫為 (b -> c) -> (a -> b) -> (a -> c) 可以使這更容易理解。）
組合和高階函式提供了一系列強大的技巧。作為一個小示例，首先考慮 inits 函式，它在 Data.List 模組中定義。引用文件，它“返回引數的所有初始段，最短的放在最前面”，因此
Prelude Data.List> inits [1,2,3] [[],[1],[1,2],[1,2,3]]
我們可以使用 Prelude 中的以下高階函式提供 inits 的單行實現（為增加戲劇效果而寫成無點形式）：flip、scanl、(.) 和 map
myInits :: [a] -> [[a]]
myInits = map reverse . scanl (flip (:)) []
一開始，吞下一個如此簡練的定義可能看起來令人生畏，因此請慢慢地，一點一點地分析它，回憶起每個函式的作用，並將型別簽名作為指導。
myInits 的定義非常簡潔和乾淨，括號使用量保持在最低限度。當然，如果一個人過度使用組合，寫出很長的 (.) 鏈，事情就會變得混亂；但是，當合理部署時，這些無點風格就顯得格外出色。此外，實現本身相當“高層次”：我們沒有明確處理諸如模式匹配或遞迴之類的細節；我們部署的函式——包括高階函式及其函式引數——負責處理這樣的底層實現細節。
($) 是一個奇特的高階運算子。它的型別是
($) :: (a -> b) -> a -> b
它將函式作為其第一個引數，它所做的全部是將函式應用於第二個引數，因此，例如，(head $ "abc") == (head "abc")。
你可能會認為 ($) 完全沒有用！但是，關於它有兩個有趣的地方。首先，($) 的優先順序非常低，[2]與具有最高優先順序的普通函式應用不同。實際上，這意味著我們可以透過使用 $ 來打破優先順序，從而避免令人困惑的括號巢狀。我們編寫了一個 myInits 的非無點版本，而無需新增新的括號
myInits :: [a] -> [[a]]
myInits xs = map reverse . scanl (flip (:)) [] $ xs
此外，由於 ($) 只是一個恰好應用函式的函式，而函式只是值，所以我們可以編寫像這樣的有趣表示式
map ($ 2) [(2*), (4*), (8*)]
（是的，這是一個函式列表，它是完全合法的。）
顧名思義，uncurry 是一個撤銷柯里化的函式；也就是說，它將一個具有兩個引數的函式轉換為一個將一對作為其唯一引數的函式。
uncurry :: (a -> b -> c) -> (a, b) -> c
Prelude> let addPair = uncurry (+) Prelude> addPair (2, 3) 5
uncurry 在野外偶爾看到的一個有趣的用法是與 ($) 相結合，這樣一來，對的第一個元素就應用於第二個元素。
Prelude> uncurry ($) (reverse, "stressed") "desserts"
還有 curry，它與 uncurry 相反。
curry :: ((a, b) -> c) -> a -> b -> c
Prelude> curry addPair 2 3 -- addPair as in the earlier example. 5
由於大多數 Haskell 函式已經柯里化，因此 curry 遠不如 uncurry 常見。
最後，我們應該提一下兩個函式，雖然它們本身不是高階函式，但最常作為高階函式的引數使用。id，即恆等函式，是一個型別為 a -> a 的函式，它會返回其引數不變。
Prelude> id "Hello" "Hello"
與 id 相似，const 是一個 a -> b -> a 函式，其工作方式如下
Prelude> const "Hello" "world" "Hello"
const 接受兩個引數，丟棄第二個引數並返回第一個引數。當被視為一個引數的函式時，a -> (b -> a)，它返回一個常數函式，無論傳入什麼引數，它始終返回相同的值。
id 和 const 一開始可能看起來毫無用處。但是，在處理高階函式時，有時需要傳遞一個虛擬函式，無論是對引數不進行任何操作的函式，還是始終返回相同值的函式。id 和 const 為我們提供了用於此類情況的便捷虛擬函式。
| 練習 |
|---|
|