Haskell高阶函数(归并排序mergesort,map,filter)

Haskell高阶函数(归并排序mergesort,map,filter)

柯里化Currying
Currying 是函数式语言（和其他语言）的一个特性，以逻辑学家 Haskell Curry 的名字命名（是的，Haskell 也是以他的名字命名的）
它是将具有多个参数的函数转换为具有单个参数的（一系列）函数的过程
Haskell 会自动完成，例如
add :: Int -> Int -> Int
add x y = x + y
被自动解释为
add :: Int -> (Int -> Int)
add = \x -> (\y -> x + y)
这只是说明“add 是一个接受整数 x 并返回另一个函数的函数，该函数又接受一个整数 y，并返回它们的和 x+y”

:type (+)
(+) :: Num a => a -> a -> a
:type (+) 2
(+) 2 :: Num a => a -> a
f = (+) 2
f 3
5

作为参数的函数
Haskell 允许您定义也将函数作为参数的函数，例如：
twice :: (a -> a) -> a -> a
twice f x = f (f x)
这个函数接受一个函数和一个值，并将函数应用到值的结果返回。

twice (*2) 3
12
twice reverse [1, 2, 3]
[1, 2, 3]

由于柯里化，我们可以部分应用两次以提供其他有用的函数，例如：四倍 = 两倍 (*2)
将函数作为参数的函数的正式术语是高阶函数

归并排序mergesort
这是一种更高级的归并排序：

这意味着 cmp 是一个函数，它接受两个参数（与列表元素的类型相同）并返回一个布尔值。 如果参数的顺序正确，则返回 true，否则返回 false。

前奏中的高阶函数Higher order functions in the prelude

更有用的高阶函数……
all, any, takeWhile, dropWhile

all even [2,4,6,8,10]
True
any (== ’ ’) “abc def”
True
takeWhile (/= ’ ’) “abc def”
“abc”
dropWhile (== ’ ’) " abc test"
“abc test”

foldr
foldr（“fold right”的缩写）是一个库函数，用于封装列表上的常见递归模式：
f [] = value
f (x:xs) = x operator (f xs)

sum [] = 0
sum (x:xs) = x + sum xs
sum = foldr (+) 0
This is the same as:
sum xs = foldr (+) 0 xs



product [] = 1
product (x:xs) = x * product xs
product = foldr (*) 1


and [] = True
and (x: xs) = x && and xs
and = foldr (&&) True

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

For example:
foldr add 0 [1, 2, 3]
= add 1 (foldr add 0 [2,3])
= 1 + (foldr add 0 [2, 3])
= 1 + (2 + (foldr add 0 [3]))
= 1 + (2 + (3 + (foldr add 0 [])))
= 1 + (2 + (3 + 0))
请注意，虽然 foldr 的定义使用函数而不是运算符（因此，当我们使用运算符时，我们将它们放在括号中）
假设我定义了一个函数 snoc，它将一个项目添加到列表的末尾而不是开头（snoc x xs = xs ++ [x]，snoc 与 cons 相反）。mystery = foldr snoc []

为什么 foldr 有用？
列表上的一些递归函数，例如 sum，使用 foldr 更容易定义。
如果使用 foldr 代替显式递归，高级程序优化会更简单。
使用 foldr 定义的函数的属性可以使用 foldr 的代数属性来证明，例如融合和香蕉分裂规则。

香蕉分裂规则
作为使用 fold 生成元组的第一个简单示例，考虑计算数字列表的总和和长度的函数 sumlength：
sumlength :: [Int] -> (Int,Int)
sumlength xs = (sum xs, length xs)
通过使用前面给出的 fold 直接组合函数 sum 和 length 的定义，函数 sumlength 可以重新定义为 fold 的单个应用程序，它从数字列表中生成一对数字：
sumlength = fold (λn (x, y) -> (n + x, 1 + y)) (0, 0)
这个定义比原始定义更有效，因为它只对参数列表进行一次遍历，而不是两次单独的遍历。从这个例子中概括，任何对 fold 应用到同一个列表总是可以组合起来，通过调用 fold 的所谓的“香蕉拆分”属性来给出一个单独的 fold 应用来生成一个对（Meijer，1992） .这个属性的奇怪名称源于这样一个事实，即折叠运算符有时使用类似于香蕉的括号 (| |) 编写，而配对运算符有时称为拆分。因此，它们的组合可以称为香蕉分裂！

foldl
foldl 是 prelude 中的另一个高阶函数，与 foldr 非常相似。 不同之处在于它捕获了左关联递归模式。
例如：

sum [1, 2, 3]
= sum’ 0 [1, 2, 3]
= sum’ (0+1) [2, 3]
= sum’ ((0+1)+2) [3]
= sum’ (((0+1)+2)+3) []
= (((0+1)+2)+3)
在实践中，foldr 和 foldl 通常是可以互换的。

今天我们介绍了：
1.高阶函数的基本概念
2.回顾我们使用过的高阶函数
3.两个新的标准函数：foldr 和 foldl