高阶函数

高阶函数 - 一个将函数作为参数或返回函数作为结果的函数，或者两者都做

高阶函数 是将一个或多个函数作为参数或返回函数作为结果的函数。三个常见的高阶函数是 map、filter 和 reduce/fold 函数

扩展：函子和非列表映射 虽然这里面的示例都是关于使用 map、filter 和 reduce/fold 函数来处理列表，但是可以用其他数据类型代替列表。例如，你可能将一个函数映射到树的元素上。在 Haskell 中，任何 函子 类型类的都可以用于 map 函数。

map 函数

map 函数 - 一个高阶函数，其中给定函数应用于给定列表的每个元素，从而产生一个新的输出列表

map 函数接收一个列表和一个要应用于列表的函数。它将这个给定函数应用于给定列表中的每个元素，创建一个新的列表，然后返回。定义 map 的另一种方式是它将给定列表的每个项目映射到输出列表

.> map (+10) [1,2,3,4,5]
[11, 12, 13, 14, 15]
.> map (^2) [20, 3, 51, 6, 3, 7]
[400,9,2601,36,9,49]

.> map (++ "!") ["scary", "weird", "spooky", "kooky"]
["scary!", "weird!", "spooky!", "kooky!"]
.> map ("NOT " ++) ["scary", "weird", "spooky", "kooky"]
["NOT scary", "NOT weird", "NOT spooky", "NOT kooky"]

.> map (replicate 2) ['a', 'b', 'c']
["aa","bb","cc"]
.> map (replicate 2) ["a", "b", "c"]
[["a","a"],["b","b"],["c","c"]]

map 也可以作用于列表的列表，其中要映射的函数依次应用于每个子列表。例如，如果你想从一组列表中找到最小值，你可以写

.> map minimum [[1, 3], [2, 7, 5],[9, 6]]
[1,2,6]

注意这里我们似乎有一个比我们开始时更小的列表。虽然就每个现在只有一个项目的内部列表的长度而言这是真的，但是传递给 map 函数的原始列表有三个项目（列表 [1, 3], [2, 7, 5], [9, 6]），并且返回的列表也有三个项目（[1,2,6]）。

filter 函数

filter 函数 - 一个高阶函数，它返回满足给定条件的给定列表的元素

filter 函数接收一个列表和过滤条件，它将过滤条件应用于列表，返回一个匹配过滤条件的项目列表。过滤条件有时被称为 谓词函数，其中从将条件应用于原始列表的每个元素返回 TRUE 或 FALSE。在 Haskell 中，这使用 filter 命令执行，例如

.> let list1 = [1,2,3,4,5,6,7,8,9]
.> filter (>5) list1

这查看 list1 中的每个项目，并检查它们是否大于 5。将那些大于 5 的设置为True，将那些小于 5 的设置为False

[1,2,3,4,5,6,7,8,9]

[F,F,F,F,F,T,T,T,T]

它返回所有设置为True的项目的列表

[6,7,8,9]

使用 odd 和 even 命令的其他 filter 示例

.> let list1 = [1,2,3,4,5,6,7,8,9]
.> let list2 = filter even list1 
.> list2
[2, 4, 6, 8]
.> filter odd list1 
[1, 3, 5, 7, 9]
.> filter odd list2
[]

其他编程语言可能没有 filter 命令，但可以通过使用 select case、switch、if then else 来实现类似的输出。

reduce 或 fold 函数

reduce/fold 函数 - 一个高阶函数，它递归地将函数应用于列表的元素，直到列表为空

reduce 或 fold 函数将列表、要应用于列表的函数和起始值作为输入。有两种类型的 fold 命令，foldl 和 foldr，这里的示例使用 foldl。

Fold 将给定函数应用于列表的第一个元素（从左开始）和起始值，然后将 fold 命令应用于此结果和列表的其余部分。它递归地执行此操作，直到 fold 命令应用于空列表，此时它返回计算的值。从 Haskell wiki 描述它的另一种方法

-- [] represents the empty list, 
-- and (x:xs) represents the list starting with x and where the rest of the list is xs. 
-- if the list is empty, the result is the initial value; else
-- we recurse immediately, making the new initial value the result
-- of combining the old initial value with the first element.
rule 1. foldl f z []     = z 
rule 2. foldl f z (x:xs) = foldl f (f z x) xs

为了实际看到这一点，看看 haskell 命令 foldl (*) 1 [1,2,3,4]，这段代码将递归地将列表的元素乘在一起

foldl (*) 1 [1,2,3,4]

这与规则 2. 匹配。f = *，z = 1，x = 1，xs = [2,3,4]。由于命令右侧的列表 xs 不是空的，因此我们执行以下操作

foldl f z (x:xs) = foldl f (f z x) xs

这使得下一个调用

foldl (*) (* 1 1) [2,3,4]

列表 xs 不是空的，因此我们再次应用规则 2.，其中 f = *，z = * 1 1，x = 2，xs = [3,4]。下一个调用是

foldl (*) (* (* 1 1) 2) [3,4]

列表 xs 不是空的，因此我们再次应用规则 2.，其中 f = *，z = * (* 1 1) 2，x = 3，xs = [4]。下一个调用是

foldl (*) (* (* (* 1 1) 2) 3) [4]

列表 xs 仍然不是空的，因此我们再次应用规则 2.，其中 f = *，z = * (* (* 1 1) 2) 3，x = 4，xs = []。因此下一个 foldl 调用是

foldl (*) (* (* (* (* 1 1) 2) 3) 4) []

列表 xs 现在是空列表 []。这与规则 1. 匹配，并且返回 z

(* (* (* (* 1 1) 2) 3) 4)

我们可以将 前缀表示法（例如 * 1 1）改写为 中缀表示法（例如 1 * 1），并从最里面的括号开始计算出括号

((((1*1)*2)*3)*4)
(((1*2)*3)*4)
((2*3)*4)
(6*4)
24

使用中缀表示法将值加在一起的更简洁的示例

foldl (+) 0 [1,2,3,4]
foldl (+) (0+1) [2,3,4]
foldl (+) ((0+1)+2) [3,4]
foldl (+) (((0+1)+2)+3) [4]
foldl (+) ((((0+1)+2)+3)+4) []
((((0+1)+2)+3)+4)
((((1)+2)+3)+4)
(((3)+3)+4)
((6)+4)
10

考试问题 什么是高阶函数？ 回答 一个将函数作为参数或返回函数作为结果的函数，或者两者都做 Haskell 命令 filter (>5) [32, 32, 1, 3, 5, 31, 3, 5, 212] 的输出是什么？ 回答 [32, 32, 31, 212] Haskell 命令 filter (odd) [32, 32, 1, 3, 5, 31, 3, 5, 212] 的输出是什么？ 回答 [1, 3, 5, 31, 3, 5] Haskell 命令 map ('+' :) ["good", "excellent", "brill"] 的输出是什么？ 回答 ["+good","+excellent","+brilliant"] 注意：在 '+' 运算符上使用单引号表示我们可以使用预置命令。它将 '+' 视为单个项目。此代码不适用于 "+"，因为它将 "+" 视为列表，而预置不能处理列表作为第一个项目。 Haskell 命令 map (+5) (filter (<30) [29, 31, 30]) 的输出是什么？ 回答 [34] foldl (+) 6 [9, 2, 13] 的结果是什么？ 回答 30 foldl (*) 1 [2, 3, 4] 的结果是什么？ 回答 24 foldl (^) 1 [2, 3, 4] 的结果是什么？ 回答 1 foldl (^) 2 [2, 1, 2, 1] 的结果是什么？ 回答 16 写下执行 foldl (^) 2 [3, 2, 1] 所涉及的所有 foldl 函数调用 回答 foldl (^) 2 [3, 2, 1] foldl (^) (2^3) [2, 1] foldl (^) ((2^3)^2) [1] foldl (^) (((2^3)^2)^1) [] (((2^3)^2)^1) (((8)^2)^1) ((64)^1) 64 描述一等对象和高阶函数之间的区别 回答 一等对象是可以作为参数传递或由函数返回的对象。高阶函数可以接受另一个函数作为参数。