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 为我们提供了用于此类情况的便捷虚拟函数。
| 练习 |
|---|
|